HDU-3746 Cyclic Nacklace 字符串匹配 KMP算法求最小循环节

题目链接：https://cn.vjudge.net/problem/HDU-3746

题意

给一串珠子，我们可以在珠子的最右端或最左端加一些珠子

问做一条包含循环珠子的项链，最少还需要多少珠子

思路

KMP的另一个用法，求最小循环节minloop=len-fail[len]

用我的观点来看KMP的fail数组，就是值域和定义域都是串的长度，返回值是这个串能够匹配后缀的最大前缀串长度

但是纯循环节构成的串中，这个返回值不包括第一个循环节

比如aabaabaab

fail[9]6 fail[6]3

提交过程


WA	没有注意至少两个循环节
AC

代码

#include <cstring>

#include <cstdio>

const int maxm=1e5+20;

char P[maxm];

int fail[maxm];

// the domain and range of fail array mean the length of correct string.

void getFail(int m){

	fail[0]=fail[1]=0;

	for (int i=1; i<m; i++){

		int j=fail[i];

		while (j && P[j]!=P[i]) j=fail[j];

		fail[i+1]=((P[i]==P[j])?j+1:0);

	}

}

int main(void){

	int T, len;

	scanf("%d", &T);

	while (T--){

		scanf("%s", P);

		getFail(len=strlen(P));

		int maxloop=len-fail[len];

		if (len%maxloop) printf("%d\n", maxloop-len%maxloop);

		else printf("%d\n", (len==maxloop)?maxloop:0);

	}

	return 0;

}

Time	Memory	Length	Lang	Submitted
109ms	1688kB	581	G++	2018-08-02 10:35:30

巴特西

HDU-3746 Cyclic Nacklace 字符串匹配 KMP算法求最小循环节

题意

思路

提交过程

代码

最新文章

热门文章

巴特西

HDU-3746 Cyclic Nacklace 字符串匹配 KMP算法 求最小循环节

题意

思路

提交过程

代码

最新文章

热门文章

HDU-3746 Cyclic Nacklace 字符串匹配 KMP算法求最小循环节