KMP

KMP 的思想

kmp的思想就是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去匹配

怎么记录之前已经匹配的内容 ？

一般使用前缀表来做记录

前缀表 ： 记录了模式串 和 文本串 不匹配的时候， 模式串应该从哪里开始重新匹配的信息

案例 （下文所有都会拿这两个举例）：

文本串 : 【 a a b a a b a a f a】

模式串 ： 【 a a b a a f】

有关前缀表

什么是前缀 ?

​ 字符串中前缀是指 不包含最后一个字符的所有以第一个字符开头的连续子字符串

以模式串为例

【a a b a a f】

它的前缀有

[ a ]

[ a a ]

[ a a b ]

[ a a b a]

[ a a b a a]

什么是后缀 ?

​ 字符串中后缀是指 不包含第一个字符的所有以最后一个字符结尾的连续子字符串

以模式串为例

【a a b a a f】

它的后缀有

[ f ]

[ a f ]

[ a a f ]

[ b a a f ]

[ a b a a f ]

最长相等前后缀

以模式串为例

【a a b a a f】 那么这个的最长相等连续字串就是 0

如果是【a a】 那么它的最长相等连续字串就是 1

如果是【a a b】 那么它的最长相等连续字串就是 0

如果是【a a b a 】 那么它的最长相等连续字串就是 1

如果是【a a b a a】 那么它的最长相等连续字串就是 2

得到前缀表

下标 ：[ 0 1 2 3 4 5 ]

模式串: [ a a b a a f ]

前缀表: [ 0 1 0 1 2 0 ] ——> 我们得到前缀表就是 最长相等前后缀 ，也就是最长相等连续子串

如何利用前缀表找到字符不匹配时指针应该移动的位置

文本串 : 【 a a b a a b a a f a】

下标 ： 【 0 1 2 3 4 5…】

模式串 : 【 a a b a a f 】

前缀表 : 【 0 1 0 1 2 0】

根据不匹配的前一位即前面匹配的那一位的最长相等前后缀的next[i] 的值 和 上面的文本串的下标 进行匹配 ，从而找到指针应该移动的位置

从上面的图中 我们就可以得到 在 文本串的【索引 5】 的地方开始就无法匹配 ， 那么我们要找的就是【索引 4】所对应的前缀表的数值

与之对应的值 为 2 那么我们就从文本串中找到下标为 2 的，从那里开始重新匹配

实现KMP

构造前缀表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void getNext(String s , int[] next){
    //初始化指针
    int j = -1;
    next[0] = j;
    
    for(int i = 0; i< s.length();i++){
        //前后缀 不相等的情况
        while( j >= 0 && s.charAt(i) != s.charAt(j + 1)){
            j = next[j];	//回退
        }
        //前后缀 相等的情况
      	if(s.charAt(i) == s.charAt(j + 1)){
            j++;
        }
        next[i] = j; //对前缀表进行赋值 ，赋值最长相等前后缀
    }
}



用前缀表来匹配数组

找出文串中 模式串第一个字符的位置（从 0 开始）

答 ： 返回当前在文本串匹配的最后一个位置 i ， 然后再减去模式串的长度 ，就是文本串中模式串的第一个字符的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//						文本串 		模式串
public int strStr(String str , String needle){
    if(needle.length() == 0){
        return 0;
    }
    int[] next = new int[needle.length()];
    int j = -1 ; 
    for(int i =0 ; i<str.length;i++){
        //不匹配情况
        while(j >= 0 && str.charAt(i) != needle.charAt( j - 1)){
            j = next[j];	//j 寻找之前匹配好的位置
        }
        //匹配的情况
        if(str.charAt(i) == needle.charAt(j - 1)){
            j++;
        }
        if(j == needle.length() - 1){
            return i - needle.length() + 1;
        }
    }
    return -1;
}