Power Strings
Time Limit:3000MSMemory Limit:65536K
Total Submissions:37817Accepted:15653
Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
abcdaaaaababab.
Sample Output
143
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
Source
AC code：
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define maxn 1000005using namespace std;int next[maxn];int main(){char s[maxn];while(scanf("%s",s)!=EOF&&strcmp(s,".")){int k=0,len=strlen(s),i,j;j=0,k=-1;next[0]=-1;while(j<len){if(k==-1||s[j]==s[k]){j++;k++;if(s[j]!=s[k])next[j]=k;else next[j]=next[k];}else k=next[k];}if(len%(len-next[len])==0)cout<<(len/(len-next[len]))<<'\12';else printf("1\n");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，前有阻碍，奋力把它冲开，运用炙热的激情，
