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.
题意：
求每个字符串最多是由多少个相同的子字符串重复连接而成的。
如：ababab 则最多有3个 ab 连接而成。
思路：两种方法求循环节的模板题。
哈希：
#include<stdio.h>
#include<string.h>
typedef unsigned long long ull;
const int N=1e6+;
char a[N];
ull p[N],sum[N],x=; void init()
{
p[]=;
for(int i=; i<N; i++)
p[i]=p[i-]*x;
} int main()
{
init();
while(~scanf("%s",a+))
{
if(a[]=='.')
break;
int len=strlen(a+);
sum[]=;
for(int i=;i<=len;i++)//主串哈希值
sum[i]=sum[i-]*x+a[i];
for(int i=; i<=len; i++)
{
if(len%i!=0)
continue;//说明不存在该循环节
int flag=;
for(int j=i; j<=len; j+=i)
{ //ababab
//i=2时 -> j=2、4、6
if((sum[j]-sum[j-i]*p[i])!=sum[i])
//(sum[2]-sum[2-2]*p[2])!=sum[2]
//(sum[4]-sum[4-2]*p[2])!=sum[2]
//(sum[6]-sum[6-2]*p[2])!=sum[2]
{
flag=;
break;
}
}
if(flag==)
{
printf("%d\n",len/i);
break;
}
}
}
return ;
}
KMP：
思想：
比如abcabcabcabc ，nextt[len]=9,len=12，所以len-next[len]=3肯定是len=12的因数，并且此时len-next[len]=3也肯定为最短循环节的长度，所以len/（len-next[len]）=12/（12-9）=12/3=4，即循环节的个数，也就是出现过几次abc。
如果不能整除说明不存在循环节，直接输出1即可。
int w=len-nextt[len];
if(len%w==)
printf("%d\n",len/w);
else
printf("1\n");
详细代码如下：
#include<stdio.h>
#include<string.h>
const int N=1e6+; int nextt[N],len;
char a[N]; void getnext()
{
int i=,j=-;
nextt[]=-;
while(i<len)
{
if(j==-||a[i]==a[j])
{
nextt[++i]=++j;
}
else
j=nextt[j];
}
} int main()
{
while(~scanf("%s",a))
{
if(a[]=='.')
break;
len=strlen(a);
getnext();
len=strlen(a);
int w=len-nextt[len];
if(len%w==)
printf("%d\n",len/w);
else
printf("1\n");
}
return ;
}