fzu1901Period II （KMP）

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1901

nex数组。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 const int maxn=1000010;
 6 char s[maxn];
 7 int nex[maxn];
 8 vector<int> ct;
 9 int n;
10 int main()
11 {
12     int t;
13     int cas=0;
14     scanf("%d",&t);
15     while(t--)
16     {
17 
18         ct.clear();
19         scanf("%s",s);
20         n=strlen(s);
21         int i=0,j=-1;
22         nex[0]=-1;
23         while(i<n)
24         {
25             if(j==-1||s[i]==s[j])
26                 nex[++i]=++j;
27             else j=nex[j];
28         }
29         for(int i=nex[n];i>0;i=nex[i])
30             ct.push_back(n-i);
31         printf("Case #%d: %d
",++cas,ct.size()+1);
32         for(int i=0;i<ct.size();i++)
33             printf("%d ",ct[i]);
34         printf("%d
",n);
35     }
36 }