Appoint description:
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).
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 指的是1-next[] 与 len-next[]-len是一样的。
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll(x) (1<<x)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int msize=1e6+9;
class KMP
{public:
int next[msize],len;
char s[msize];
void getnext()
{ int j=0,k=-1;
len=strlen(s);
next[j]=-1;
while(j<len)
{
if(k==-1||s[j]==s[k])
{
++j;++k;
next[j]=k;
}
else k=next[k];
}
}
void getans()
{int ans;
getnext();
if(len%(len-next[len])==0)
ans=len/(len-next[len]);
else ans=1;
printf("%d\n",ans);
}
};
KMP s;
int main()
{// freopen("data.in","r",stdin);
while(~scanf("%s",s.s))
{
if(s.s[0]=='.')break;
s.getans();
}
}