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.
题目大意：给一个字符串，问这个字符串是否能由另一个字符串重复R次得到，求R的最大值。
思路：对于一个字符串，如abcd abcd
abcd，由长度为4的字符串abcd重复3次得到，那么必然有原字符串的前八位等于后八位。
也就是说，对于某个字符串S，长度为N，由长度为n的字符串s重复R次得到，当R≥2时必然有S[1..N-n]=S[n+1..N]。
那么对于KMP算法来说，就有fail[N]=N-n。此时n肯定已经是最小的了。
然后只需要判断N是否n的倍数，是则输出N/n即可。否则输出1。
代码（157MS）：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 7 const int MAXN = 1000010; 8 9 void getFail(char *P, int m, int f[]) { 10 f[0] = f[1] = 0; 11 for(int i = 1; i < m; ++i) { 12 int j = f[i]; 13 while(j && P[i] != P[j]) j = f[j]; 14 f[i + 1] = (P[i] == P[j] ? j + 1 : 0); 15 } 16 } 17 18 char s[MAXN]; 19 int fail[MAXN], n; 20 21 int main() { 22 while(scanf("%s", s) != EOF) { 23 if(*s == ‘.‘) break; 24 n = strlen(s); 25 getFail(s, n, fail); 26 if(n % (n - fail[n]) == 0) printf("%d\n", n / (n - fail[n])); 27 else puts("1"); 28 } 29 }