POJ 2406 Power Strings

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<map>
 5 #define maxn 10010000
 6 using namespace std;
 7 char p[maxn];
 8 int next[maxn],len;
 9 int kmp(){
10     int i=0,j=-1;
11     next[0]=-1;
12     while(i<len){
13         if(j==-1||p[i]==p[j]) next[++i]=++j;
14         else j=next[j];
15     }
16 }
17 int main()
18 {
19     while(scanf("%s",p)!=EOF&&p[0]!=‘.‘){
20         len=strlen(p);
21         kmp();
22         if(len%(len-next[len]))printf("1\n");
23         else printf("%d\n",len/(len-next[len]));
24     }
25     return 0;
26 }