poj 2406Power Strings

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 1000010
 5 using namespace std;
 6 char s[maxn];
 7 int next[maxn];
 8 void get(char *s,int *next)
 9 {
10     int j,k;
11     next[0]=-1;
12     j=0;
13     k=-1;
14     int kk=strlen(s);
15     while(j<kk)
16     {
17         if(k==-1||s[j]==s[k])
18         {
19             j++;
20             k++;
21             next[j]=k;
22         }
23         else
24             k=next[k];
25     }
26 }
27 int main()
28 {
29     while(scanf("%s",s)!=EOF)
30     {
31         if(!strcmp(s,".")) break;
32         get(s,next);
33         int k=strlen(s);
34         if(k%(k-next[k])==0)
35             printf("%d
",k/(k-next[k]));
36         else
37             printf("1
");
38     }
39     return 0;
40 }
View Code