[HDU-3746] Cyclic Necklace KMP找循环

题面

HDU-3746

大意:求出添加尽可能少的字符数量使得原串成为循环串.

比如abca->abcabc要2个字符.

分析

KMP找循环节!fail数组的巧用

比如说题目中这样的串abca的fail数组为[0,0,0,1].也就是说最后一位为1其他均为0.

我们根据fail数组的定义就很容易推出答案

1.如果fail[len]为0,也就是说没有任何的匹配.就是原字符串长度.

2.如果fail[len]不为0,我们用len-fail[len]得到一个循环节.然后如果这个循环节是len的因子.也就是恰好出现了循环.那么不要添加任何的字符,return 0.否则返回该添加的量.也就是循环长度减去存在的残缺循环长度

具体代码说明一切.

代码

#include<bits/stdc++.h>
using namespace std;
char s[100010];
int fail[100010];
int kmp(char *b,int nb)
{
	memset(fail,0,sizeof(fail));
	for (int i = 2; i <= nb; i++)
	{
		int j = fail[i-1];
		while(j != 0 && b[j+1] != b[i]) j = fail[j];
		if (b[j+1] == b[i]) fail[i] = j+1;
		else fail[i] = 0;
	}	
	if (fail[nb] == 0) return nb;
	int t = nb - fail[nb];
	if (nb % t == 0) return 0;
	return (t-nb%t); 
}

int main(int argc, char *argv[])
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s+1);
		printf("%d\n",kmp(s,strlen(s+1)));
	}
	return 0;
}