|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cstring> #include <cstdio> #include <string> using namespace std; int lps[1000005]; void prefixArray(string s) { memset(lps,0,sizeof(lps)); int len=0;//length of prev longest prefix int i=1; lps[0]=0; int length = s.size(); while(i<length) { if(s[i]==s[len]) { len+=1; lps[i]=len; i+=1; } else { if(len!=0) { len = lps[len-1]; } else { lps[i]=0; i+=1; } } } } int main() { string s; int lastval,minimal_length_of_repeated_string; while(cin>>s) { if(s==".") break; prefixArray(s); lastval = lps[s.size()-1]; minimal_length_of_repeated_string = s.size()-lastval; if(s.size()%minimal_length_of_repeated_string==0) printf("%d\n",s.size()/minimal_length_of_repeated_string); else printf("1\n"); } return 0; } |