hdu 1358 Period （（KMP算法）求循环节的个数）

题目链接

 

题意是求前n个数的循环节的个数：

例如：aabaabaabaab中 ，

前2个字符aa，循环节为a, 所以为2 2；

前6 个 字符循环节为aab,  所以为6 2；

前9个 字符循环节为aab,   所以为9 3；

前12 个 字符循环节为aab,所以为12 4；

 

关键是如何求循环节，首先还要熟悉next数组的意思，next[j]=k,表示j前面k个元素与开头的前k个元素相同，但是中间可能有循环的元素，如何去除重复的元素

i	0	1	2	3	4	5	6	7	8	9	10	11	12
a[i]	a	a	b	a	a	b	a	a	b	a	a	b
next[i]	-1	0	1	0	1	2	3	4	5	6	7	8	9

 

 2*next[i]-i即可以求出中间重复的元素；

（原因：初中因该学过，给N个元素，前k个元素和后k个元素相等，求重复的元素个数）

next[i]-(2*next[i]-i) == i-next[i]即是最小的循环节；

i/最小循环节  =  循环的次数 ；

 

 

#include<cstdio>
#include<cstring>
using namespace std;

const int MAX = 1000000 + 5;
int next[MAX],len;
char a[MAX];

void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<len) 
	{
		while(j>-1&&a[j]!=a[i])
			j=next[j];
		j++;
		i++;
		next[i]=j;
	}
}

int main()
{
	int ncase=0;
	while(scanf("%d",&len)&&len)
	{
		scanf("%s",a);
		int circle; 
		get_next();
		printf("Test case #%d\n",++ncase);
		for(int i=1;i<=len;i++)
		{
			circle=next[i]-(2*next[i]-i);
			if(2*next[i]-i>=0 && i%circle == 0)
			{
				printf("%d %d\n",i,i/circle);
			}
		}
		printf("\n");
	}
	return 0;
}