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数组

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <set>

 #include <string>

 using namespace std;

 #define MP make_pair

 #define PB push_back

 typedef long long LL;

 const double eps=1e-;

 const int K=1e6+;

 const int mod=1e9+;

 int nt[K],ans[K];

 char sa[K];

 void kmp_next(char *T,int *next)

 {

     next[]=;

     for(int i=,j=,len=strlen(T);i<len;i++)

     {

         while(j&&T[i]!=T[j]) j=next[j-];

         if(T[i]==T[j])  j++;

         next[i]=j;

     }

 }

 int kmp(char *S,char *T,int *next)

 {

     int ans=;

     int ls=strlen(S),lt=strlen(T);

     for(int i=,j=;i<ls;i++)

     {

         while(j&&S[i]!=T[j]) j=next[j-];

         if(S[i]==T[j])  j++;

         if(j==lt)   ans++;

     }

     return ans;

 }

 int main(void)

 {

     int t,cnt=;cin>>t;

     while(t--)

     {

         scanf("%s",sa);

         kmp_next(sa,nt);

         int len=strlen(sa),k=;

         int tk=len;

         while(nt[tk-]>)

             ans[k++]=len-nt[tk-],tk=nt[tk-];

         ans[k++]=len;

         printf("Case #%d: %d\n",cnt++,k);

         for(int i=;i<k;i++)

             printf("%d%c",ans[i],i!=k-?' ':'\n');

     }

     return ;

 }

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