学步园

http://acm.hdu.edu.cn/showproblem.php?pid=3746

/* 通过KMP中的 next 数组求最小循环节 */

题目要求：给出一个字符串，求出将字符串的全部字符最少循环2次需要添加的字符数。

#include<stdio.h>
#include<string.h>
int next[100005];
char s[100005];
void getnext(int len)
{
	int i,j;
	for(i=0,j=-1,next[0]=-1;i<len;){
		if(j==-1||s[i]==s[j]){
			i++;
			j++;
			next[i]=j;
		}
		else
			j=next[j];
	}
}
int main()
{
	int T,length,len;
	scanf("%d",&T);
	getchar();
	while(T--){
		gets(s);
		len=strlen(s);
		getnext(len);
		length=len-next[len];  //length为最小循环节的长度
		if(len%length==0){
			if(len==length)
				printf("%d\n",length);
			else
				printf("0\n");
		}
		else{
			printf("%d\n",length-(next[len]%length));
		}
	}
	return 0;
}