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
abcd aaaa ababab .
Sample Output
1 4 3
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int next[1100000] ; char str[1100000] ; void getnext(int len) { int i=0,j=-1; next[0]=-1; while(i<len) { if(j==-1||str[i]==str[j]) { i++; j++; next[i]=j; } else j=next[j]; } } int main() { int l , m ; while(scanf("%s", str)!=EOF) { if( str[0] == '.' ) break; l = strlen(str); getnext(l) ; m = next[l]; //if(整个串是用循环节组成的),(l-m)为最小循环节 if( l % (l-m) != 0 )//判断最小循环节会被n整除 printf("1\n"); else { m = l / ( l-m ); printf("%d\n", m); } memset(str,0,sizeof(str)); } return 0; }