[POJ 2406]Power Strings

danihao123 posted @ 2016年9月18日 12:25 in 题解 with tags POJ KMP 循环节问题 , 745 阅读

转载请注明出处：http://danihao123.is-programmer.com/

循环节又一题……用KMP性质搞搞即可。

注意特判（好像是句废话），再就没啥了……

代码：

#include <cstdio>
#include <cstring>
const int maxn=1e6+5;
char P[maxn];
int f[maxn];
int main(){
	register int i,j,xhj,n;
	while(scanf("%s",P)){
		if(P[0]=='.')
			break;
		n=strlen(P);
		f[0]=f[1]=0;
		for(i=1;i<n;i++){
			j=f[i];
			while(j && P[j]!=P[i])
				j=f[j];
			f[i+1]=(P[j]==P[i]?j+1:0);
		}
		xhj=n-f[n];
		if(!(n%xhj)){
			printf("%d\n",n/xhj);
		}else{
			puts("1");
		}
	}
	return 0;
}