poj2406 Power Strings

考虑一下：

ababab
  ababab

和

abababa
  abababa

就明白了

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int len, nxt[1000005];
char a[1000005];
void mkkmp(){
	int k=0;
	for(int i=2; i<=len; i++){
		while(k && a[i]!=a[k+1])	k = nxt[k];
		if(a[i]==a[k+1])	nxt[i] = ++k;
	}
}
int main(){
	while(scanf("%s", a+1)){
		if(a[1]=='.')	break;
		len = strlen(a+1);
		mkkmp();
		int ans=1;
		if(len%(len-nxt[len])==0)	ans = len / (len - nxt[len]);
		printf("%d
", ans);
		memset(nxt, 0, sizeof(nxt));
	}
	return 0;
}