fzu1901Period II

地址：http://acm.fzu.edu.cn/problem.php?pid=1901

题目：

Problem 1901 Period II

Accept: 442 Submit: 1099
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

For each prefix with length P of a given string S,if

S[i]=S[i+P] for i in [0..SIZE(S)-p-1],

then the prefix is a “period” of S. We want to all the periodic prefixs.

Input

Input contains multiple cases.

The first line contains an integer T representing the number of cases. Then following T cases.

Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.

Output

For each test case, first output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.

Sample Input

4 ooo acmacmacmacmacma fzufzufzuf stostootssto

Sample Output

Case #1: 3 1 2 3 Case #2: 6 3 6 9 12 15 16 Case #3: 4 3 6 9 10 Case #4: 2 9 12

Source

FOJ有奖月赛-2010年05月

思路：next数组

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <set>
 5 #include <string>
 6 using namespace std;
 7 
 8 #define MP make_pair
 9 #define PB push_back
10 typedef long long LL;
11 const double eps=1e-8;
12 const int K=1e6+7;
13 const int mod=1e9+7;
14 
15 int nt[K],ans[K];
16 char sa[K];
17 void kmp_next(char *T,int *next)
18 {
19     next[0]=0;
20     for(int i=1,j=0,len=strlen(T);i<len;i++)
21     {
22         while(j&&T[i]!=T[j]) j=next[j-1];
23         if(T[i]==T[j])  j++;
24         next[i]=j;
25     }
26 }
27 int kmp(char *S,char *T,int *next)
28 {
29     int ans=0;
30     int ls=strlen(S),lt=strlen(T);
31     for(int i=0,j=0;i<ls;i++)
32     {
33         while(j&&S[i]!=T[j]) j=next[j-1];
34         if(S[i]==T[j])  j++;
35         if(j==lt)   ans++;
36     }
37     return ans;
38 }
39 
40 
41 int main(void)
42 {
43     int t,cnt=1;cin>>t;
44     while(t--)
45     {
46         scanf("%s",sa);
47         kmp_next(sa,nt);
48         int len=strlen(sa),k=0;
49         int tk=len;
50         while(nt[tk-1]>0)
51             ans[k++]=len-nt[tk-1],tk=nt[tk-1];
52         ans[k++]=len;
53         printf("Case #%d: %d
",cnt++,k);
54         for(int i=0;i<k;i++)
55             printf("%d%c",ans[i],i!=k-1?' ':'
');
56     }
57     return 0;
58 }