|
Power Strings
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
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
/*
kmp算法的应用,next数组的应用;这种用法貌似的个定理：如果串s的长度为len, len % (len - next[len])==0,就说明这个串里面存在循环节,循环节的个数为，len / (len - next[len]) ;
*/
//还有就是这里用了next[]的修正算法，看大牛们用的都是普通求next[]的算法,poj1961这一题用修正后的next[]结果反而不对；
<span style="font-size:18px;"><span style="font-size:18px;"></span>
<span style="font-size:18px;">#include<stdio.h>
#include<string.h>
int next[1000010];
char str[1000010];
int len;
int gnext()
{
int i,j;
len = strlen(str);
i = 1;j=0;
next[1]=0;
while(i<len)
{
if(j==0||str[i]==str[j])
{
i++;j++;
if(str[i]!=str[j])
next[i] = j;
else
next[i] = next[j];
//printf("next[%d] = %d\n",i,next[i]);
}
else
j = next[j];
}
return next[len];
}
int main()
{
while(gets(str)&&str[0]!='.')
{
memset(next,0,sizeof(next));
int d = gnext();
if(len%(len-d)==0)
printf("%d\n",len/(len-d));
else
printf("1\n");
}
return 0;
}</span></span>
| 
转播
