POJ1961 Period

同UVa 1328

http://www.cnblogs.com/SilverNebula/p/5550595.html

写一半才想起来这题以前做过……

kmp求循环节

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 const int mxn=1000200;
 9 char s[mxn];
10 int next[mxn];
11 int n;
12 int main(){
13     int i,j;
14     int cas=0;
15     while(scanf("%d",&n) && n){
16         printf("Test case #%d
",++cas);
17         scanf("%s",&s);
18         next[0]=0;
19         next[1]=0;
20         j=0;
21         for(i=1;i<n;i++){
22             j=next[i];
23             while(s[j]!=s[i] && j)j=next[j];
24             if(s[j]==s[i])j++;
25             next[i+1]=j;
26         }
27         for(i=2;i<=n;i++){
28             if(next[i] && i%(i-next[i])==0)
29                 printf("%d %d
",i,i/(i-next[i]));
30         }
31         printf("
");
32     }
33     return 0;
34 }