【kmp算法】poj2406 Power Strings

如果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-next[n])==0 ? n/(n-next[n]) : 1);
	  }
	return 0;
}