学步园

这道题目也是运用next值的一道题目,我发现,运用next[]的题目真的很多,,,

今天也是搞了一天的next函数了....懂是有些懂了,.,,但是猛地把自己的原来的编程习惯变了 还 是有点不适应的,,

但是确实两种理解方法都可以,,但是 还是现在用的这个getnext好用一些,,自己可以做出简单的证明,

而这道题目,就是让你求不能重复利用的最大循环节是多少,

可以利用最后一个的后一个next值算处理,,其实大家都知道next保留的值就是前面的最长字母序列数.

求出来循环节之后,剩下的就好说了.

大家看看代码,我也参考了我的一位学长的代码的

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

char pat[100005];

int next[100005];

int len;

int getnext()
{
	int i=1,j=0;
	next[1]=0;
	while(i<=len)
	{
		if(j==0||pat[i]==pat[j])
		{
			i++,j++;
			next[i]=j;
		}
		else
			j=next[j];
	}
	return next[len+1];
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",pat+1);
		pat[0]='#';
		len=strlen(pat)-1;
		int temp=getnext();
	//	printf("%d\n",temp);
		int ans=len-(temp-1);//temp-1 是循环节
		printf(len>ans&&len%ans==0?"0\n":"%d\n",ans-len%ans);
	}
	return 0;
}