首先来写最大公共前缀和后缀，这里pa代表要找的字符串，p表示pa字符串里的每个位置的最大公共前缀和后缀表
#include<bits/stdc++.h> using namespace std; void pp(char pa[],int p[],int n) { p[0]=0; int len =0; int i=1; while(i<n) { // cout<<i<<" "<<len<<endl; if(pa[i]==pa[len]) { len++; p[i]=len; i++; } else { if(len>0)//这里没有i++，就是为了找到合适的len { len=p[len-1]; } else//注意这是对于第一项和第二项， { p[i]=len; i++; } } } } int main() { char pa[]="ABABCABAA"; int p[9]; int n=9; pp(pa,p,n); for(int i=0;i<n;i++) { cout<<p[i]<<endl; } return 0; }对于前缀表都是写成第一个是-1的形式
#include<bits/stdc++.h> using namespace std; void pp(char pa[],int p[],int n) { p[0]=0; int len =0; int i=1; while(i<n) { // cout<<i<<" "<<len<<endl; if(pa[i]==pa[len]) { len++; p[i]=len; i++; } else { if(len>0)//这里没有i++，就是为了找到合适的len { len=p[len-1]; } else//注意这是对于第一项和第二项， { p[i]=len; i++; } } } } void movee(int p[],int n) { for(int i=n-1;i>0;i--) p[i]=p[i-1]; p[0]=-1; } int main() { char pa[]="ABABCABAA"; int p[9]; int n=9; pp(pa,p,n); movee(p,n); for(int i=0;i<n;i++) { cout<<p[i]<<endl; } return 0; } #include<bits/stdc++.h> using namespace std; void pp(char pa[],int p[],int n) { p[0]=0; int len =0; int i=1; while(i<n) { // cout<<i<<" "<<len<<endl; if(pa[i]==pa[len]) { len++; p[i]=len; i++; } else { if(len>0)//这里没有i++，就是为了找到合适的len { len=p[len-1]; } else//注意这是对于第一项和第二项， { p[i]=len; i++; } } } } void movee(int p[],int n) { for(int i=n-1;i>0;i--) p[i]=p[i-1]; p[0]=-1; } void kmp(char text[],char pa[]) { int n=strlen(pa); int m=strlen(text); int *p=(int*)malloc(sizeof(int)*n); pp(pa,p,n); movee(p,n); int i=0; int j=0; while(i<m)//这里面i是一直往后移动的，j要是变了那就从就对于i的值往后比 { if(j==n-1&&text[i]==pa[j]) { cout<<"find"<<i-j<<endl; j=p[j];//注意这里和下面是一样的 } if(text[i]==pa[j]) { i++; j++; } else { j=p[j]; if(j==-1) { i++; j++; } } } } int main() { char pa[]="ABABCABAA"; char text[]="ABABABCABAABABABAB"; kmp(text,pa); return 0; }