P3375 KMP（字符串）

 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 }