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
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
KMP 感觉next数组才是本体，很重要，一定要理解其含义。
next 数组 ： next[i] 表示的是从[0,i-1] 前缀和后缀的最大匹配长度。
本题就是利用这个 next 来求最小循环节。
网上找了个好理解的 证明
例子证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
代码
#include<cstring>
#include<cstdio>
using namespace std ;
typedef long long LL ;const int MAXN = 1000000+10 ;
const int MAXM = 1e5 ;
const int mod = 1e9+7;char str[MAXN];
int nexts[MAXN];
int n,m;
void getnexts(){int i,j;i=j=0;nexts[0]=-1;j=-1;while(i<m){if(j==-1||str[i]==str[j]) nexts[++i]=++j;else j=nexts[j];}
}int main(){while(scanf("%s",str)&&str[0]!='.'){m=strlen(str);getnexts();if(m%(m-nexts[m])||!nexts[m]) puts("1");else printf("%d\n",m/(m-nexts[m]));}return 0;
}
}