1 #include<iostream> 2 using namespace std; 3 const int N=1000000+100; 4 int f[N]; 5 int main(void) 6 { 7 string s1,s2; 8 cin>>s1>>s2; 9 f[0]=-1;//f[0]置为-1，好判边界 10 int len2=s2.length(); 11 //因为f[0]=-1，所以f数组每个都比实际值小一 12 for(int i=1;i<len2;i++)//计算后len2-1的f值 13 { 14 int j=f[i-1];//f[i-1]表示前i-1个，前后缀相同的最长是多少，而我们要求的时前i个，只需判断第i个和f[i-1]+1是否相同 15 while(s2[j+1]!=s2[i]&&j>=0)//这个循环只是为了让长度为一的前后缀正确，试试ECAEE就知道了 16 { 17 j=f[j]; 18 } 19 if(s2[j+1]==s2[i]) 20 f[i]=j+1; 21 else 22 f[i]=-1; 23 } 24 //以上计算f数组 25 int len1=s1.length(); 26 for(int i=0,j=0;i<len1;)//使用f数组进行kmp匹配，至于为什么可以不回溯的证明我是真的看不懂 27 { 28 if(s1[i]==s2[j]) 29 { 30 i++; 31 j++; 32 if(j==len2) 33 { 34 cout<<i-len2+1<<endl; 35 j=f[j-1]+1; 36 } 37 } 38 else 39 { 40 if(j==0) 41 i++; 42 else 43 j=f[j-1]+1; 44 } 45 } 46 for(int i=0;i<len2;i++) 47 { 48 cout<<f[i]+1<<" "; 49 } 50 return 0; 51 }
KMP是一个比较简单的算法，但是网上的f数组的种类是真的多，建议就只看一篇
这篇我觉得是最好的了
https://blog.csdn.net/f1033774377/article/details/82556438