http://poj.org/problem?id=2406
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\n",k/(k-next[k])); 36 else 37 printf("1\n"); 38 } 39 return 0; 40 }