本文基于https://blog.csdn.net/v_july_v/article/details/7041827和《算法竞赛入门经典训练指南》
注意:有时可能会编译错误,因为next可能是关键字,此时改变一下next数组的名字就行了
下面这个kmp可以求出模板串在文本串中第一个匹配的位置，也可以在return那改成记录位置最后结束时返回一个位置数组来得到所有匹配位置
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int amn=1e5+5; 4 int next[amn]; 5 6 void GetNext(char *p,int next[]){ 7 int plen=strlen(p); 8 next[0]=-1; ///next是上一个字符对应的前缀等于后缀的最长长度 9 int k=-1,j=0; ///因为字符串下标从0开始，所以最长长度也是前缀最后一个字符的下一个字符的下标（index）（前缀与后缀相等的最长长度0对应第一个字符，1对应第2个...这样保证这一位之前的字符是匹配的（因为现在已经知道前缀与后缀匹配）) 10 while(j<plen-1){ ///k是上一个状态的next,若j==plen-1则此为是最后一个字符，其后没有字符，故不需求出下一个字符的next 11 if(k==-1||p[j]==p[k]){///k==-1在前面判断为真就直接执行下一条语句而不会造成数组越界 12 k++,j++; 13 if(p[j]!=p[k]) 14 next[j]=k; 15 else ///若p[j]==p[k]且p[j]!=s[i],则下次用p[k]匹配仍是失效的，故要用p[next[k]](若p[j]!=p[next[k]]来和s[i]匹配 16 next[j]=next[k]; 17 } 18 else k=next[k]; 19 } 20 } 21 int kmp_search(char *s,char *p){ 22 int slen=strlen(s),plen=strlen(p); 23 int i=0,j=0; 24 while(i<slen&&j<plen){ 25 if(j==-1||s[i]==p[j])i++,j++; 26 else j=next[j]; 27 } 28 if(j==plen)return i-j; ///这个可以求出模板串在文本串中第一个匹配的位置，也可以在return那改成记录位置最后结束时返回一个位置数组来得到所有匹配位置 29 else return -1; 30 } 31 int main(){ 32 char s[]="hello",p[]="ll"; 33 GetNext(p,next); 34 printf("pos: %d ",kmp_search(s,p)); 35 }
下面这个kmp返回的是t与p最后一个不匹配的位置,用来去除t的后缀与p的前缀相同的部分(就是去重),同时在函数中减少了strlen的调用，这样在模板串比较多时不容易TLE
例题参见 Codeforces 1200E
http://codeforces.com/contest/1200/problem/E
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int amn=1e6+5; 4 char ans[amn],in[amn]; 5 int nex[amn],len,tp; 6 void getnex(char p[]){ ///不要在这调用strlen!!!,用已有的就好了,不然会T到自闭!!! 7 nex[0]=nex[1]=0; 8 for(int i=1;i<len;i++){ 9 int j=nex[i]; 10 while(j&&p[i]!=p[j])j=nex[j]; 11 nex[i+1]=p[i]==p[j]?j+1:0; 12 } 13 } 14 int kmp(char t[],char p[]){ ///不要在这调用strlen!!!,用已有的就好了,不然会T到自闭!!! 15 getnex(in); 16 int j=0; 17 for(int i=pos;i<tlen;i++){ 18 while(j&&p[j]!=t[i])j=nex[j]; 19 if(p[j]==t[i])j++; 20 } 21 return j; ///这里返回的是t与p最后一个不匹配的位置,用来去除t的后缀与p的前缀相同的部分(就是去重),例题参见 Codeforces 1200E 22 } 23 int main(){ 24 cin>>t>>p; 25 tlen=strlen(t),plen=strlen(p); ///在这里调用strlen就行了,不然如果模板串太多的话调用太多strlen会TLE 26 } 27 /** 28 返回的是t与p最后一个不匹配的位置,用来去除t的后缀与p的前缀相同的部分(就是去重),同时在函数中减少了strlen的调用，这样在模板串比较多时不容易TLE 29 例题参见 Codeforces 1200E 30 http://codeforces.com/contest/1200/problem/E 31 **/