`

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;
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics