KMP算法

KMP有什么用

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

说人话就是上面第二行的f那边不相等

然后会跳到b那边

为什么直接跳到b那边了呢？

那么就往前看它的子字符串：aabaa

子字符串的前缀是aa

子字符串的后缀也是aa

那么就找到这个后缀(aa)与之相等的前缀(aa)的后面(b)重新开始匹配

(找最长相等前后缀)

0 1 2 3 4 5
a a b a a f
0 1 0 1 2 0 
因为 f 不同 就找到前面冲突的前一位 2
所以再从b开始

什么是前缀表

什么是前缀

A:只包含首字母不包含尾字母的所有字串

EX:字符串aabaaf
它的前缀为：
a
aa
aab
aaba
aabaa

什么是后缀

A:只包含尾字母不包含首字母的所有字符串

EX:字符串aabaaf
它的后缀为：
f
af
aaf
baaf
avaaf

next数组就是一个前缀表（prefix table）

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

要在文本串：aabaabaafa 中查找

是否出现过一个模式串：aabaaf。

​ a a b a a f

前缀表就是【0,1,0,1,2,0】

最长公共前后缀？

a  		0
aa 		1
aab		0
aaba 	1
aabaa	2
aabaaf  0

用next数组表示前缀表

void getNext(int* next,const string& s){
    int j=0;
    next[0]=0;
    for(int i=1;i<s.size();i++){
        while(j>0&&s[i]!=s[j]){
            j=next[j-1];
        }
        if(s[i]==s[j]){
            j++;
        }
        next[i]=j;
    }
}

28. 找出字符串中第一个匹配项的下标

class Solution{
public:
    void getNext(int* next,const string& s){
        int j=-1;
        next[0]=j;
        for(int i=1;i<s.size();i++){
            while(j>=0&&s[i]!=s[j+1]){ //
                j=next[j];  //一旦不一样，就直接往前回退
            }
            if(s[i]==s[j+1]){ //找到相同的
                j++；
            }
            next[i]=j;//将j(前缀的长度)赋值给next[i]
        }
    }
    int strStr(string haystack,string needle){
		if(needle.size()==0){
            return 0;
        }
        int next[needle.size()];//定义了一个名为next的整数数组
        getNext(next,needle);
        int j=-1;
        for(int i =0;i<haystack.size();i++){//注意i从0开始
            while(j>=0 && haystack[i]!=needle[j+1]){ //不匹配
                j=next[j]; //j寻找之前匹配的位置
            }
            if(haysyack[i]==needle[j+1]){//匹配，j和i同时向后移动
                j++;  //i的增加在foe循环里
            }
            if(j==(needle.size()-1)){//文本串里s出现了模式串t
                return  (i-needle.size()+1);  
                // aabbaaaf
                // baa   5-3+1=3
            }
		}
        return -1;
    }
}

aabaaf

s[j+1] j s[i] s[j+1] s[i] next[0]=-1 now_j

0 -1 1 (a,a) next[1]=now_j=0 0

1 0 2 (a,b) next[2]=next[0]=-1 j=next[0]=-1

0 -1 3 (a,a) next[3]=0 j=j++=0

1 0 4 (a,a) next[4]=1 j++=1

2 1 5 (b,f) next[5]= j=next[1]=0

1 0 5 （a,f） next[5]=-1 j=next[0]=-1

-1 0 -1 0 1 -1

建议手动模拟一边