题目链接：
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
abcd
aaaa
ababab
.
Sample Output
1
4
3
/*************************************************************************
> File Name: poj_2406.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年03月16日 星期三 13时19分57秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1000086;
char a[N];
int nxt[N];
void getnxt()
{
int m = strlen(a);
int k = 0;
memset(nxt, 0, sizeof(nxt));
for(int i = 1; i < m ; i++)
{
while(k&& a[k] != a[i]) k = nxt[k-1];
if(a[k] == a[i]) k++;
nxt[i] = k;
}
}
int main()
{
while(~scanf("%s", a) && a[0] != '.')
{
getnxt();
int m = strlen(a);
int t = m - nxt[m-1];
if( m % t == 0)
printf("%d\n", m / t);
else
printf("1\n");
memset(a, 0, sizeof(0));
}
return 0;
}