LA 3026 - Period KMP

看题传送门：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1027

给定一个长度为n的循环节，求它的每个前缀的最短循环节。换句话说,对于每个i （2<=i<=n），求一个最大的整数K>1（如果k处在），使得s的前i个字符组成的前缀是某个字符串重复K次得到。输出所有存在K的i对应的K。

比如aabaabaabaab只有当 i=2 6 9 12时k存在，且分别为2,2,3,4

分析：

用KMP求得失配函数f为

j: 0 1 2 3 4 5 6 7 8 9 10 11 12

P a a b a a b a a b a a b

f 0 0 1 0 1 2 3 4 5 6 7 8 9

可以看出，如果它是一个循环节，那么有 i%(i-f[i])==0

为什么会这样？

KMP原来是模板串和文本串之间的匹配关系，而失配函数是模板串自身（将自身平移f[i]，看是否能匹配）这题省略了文本串，可将文本串看做模板串，错位的部分即为i-f[i]，如果这i 个组成循环节，那么 i - f[i]这部分必然也是循环节。

为什么这样？下面摘自http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

-----------------------

k m x j i

由上，next【i】=j，两段红色的字符串相等（两个字符串完全相等），s[k....j]==s[m....i]

设s[x...j]=s[j....i](xj=ji)

则可得，以下简写字符串表达方式

kj=kx+xj;

mi=mj+ji;

因为xj=ji，所以kx=mj，如下图所示

-------------

k m x j

看到了没，此时又重复上面的模型了，kx=mj，所以可以一直这样递推下去

所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);

#include<cstdio>

const int MAXN=1000000+10;

char p[MAXN];

int f[MAXN];

void getfail(const int &n)

{

	f[0]=f[1]=0;

	for(int i=1;i<n;i++)

	{

		int j=f[i];

		while(j > 0 && p[i]!=p[j]) j=f[j];

		if(p[i]==p[j]) j++;

		f[i+1]=j;

	}

}

int main()

{

	int n;

	int kase=1;

	while(scanf("%d",&n),n)

	{

		scanf("%s",p);

		getfail(n);

		printf("Test case #%d\n",kase++);

		/*

		for(int i=0;i<n;i++)

			printf("%d ",f[i]);

		printf("\n");

		*/

		for(int i=0;i<=n;i++)

		{

			if(f[i] >0 && i%(i-f[i])==0)

				printf("%d %d\n",i,i/(i-f[i]));

		}

		printf("\n");

	}

}

巴特西

LA 3026 - Period KMP

最新文章

热门文章