poj2752Seek the Name, Seek the Fame（KMP）

KMP的nex数组。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 const int maxn=400010;
 6 char s[maxn];
 7 int nex[maxn];
 8 vector<int> cr;
 9 int n;
10 
11 int main()
12 {
13     while(scanf("%s",s)!=EOF)
14     {
15         cr.clear();
16         n=strlen(s);
17         int i=0,j=-1;
18         nex[0]=-1;
19         while(i<n)
20         {
21             if(j==-1||s[i]==s[j])
22                 nex[++i]=++j;
23             else j=nex[j];
24         }
25         cr.push_back(n);
26         for(int i=nex[n];i>0;i=nex[i])
27             cr.push_back(i);
28         for(int i=cr.size()-1;i>=1;i--)
29             printf("%d ",cr[i]);
30         printf("%d
",cr[0]);
31     }
32 }