如果next[n]<n/2,一定无解。
否则,必须要满足n mod (n-next[n]) = 0 才行,此时,由于next数组的性质,0~n-next[n]-1的部分一定是最小循环节。
[ab ababababab ab]
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000010];
int next[1000010];
void GetFail(char P[],int next[])//next[i]表示s[0]~s[i-1]的前缀中,最大相等的前后缀的长度是多少
{
next[0]=-1;
int len=strlen(P);
for(int i=0;i<len;i++)
{
int j=next[i];
while(j>=0&&P[i]!=P[j])
j=next[j];
if(j!=-1 && P[i]==P[j])
next[i+1]=j+1;
else next[i+1]=0;
}
}
int main()
{
//freopen("poj2406.in","r",stdin);
while(1)
{
scanf("%s",s);
int n=strlen(s);
if(s[0]=='.' && n==1)
break;
GetFail(s,next);
printf("%d\n",n%(n-next[n])==0 ? n/(n-next[n]) : 1);
}
return 0;
}