HDU 3746 Cyclic Nacklace / KMP

首先 t = n-next[n]是周期 n是字符串长度 如果 n%t = =0 那么该字符串是一个周期串

如果n%t !=0  t还是周期 只不过末尾多一部分 话句话说 该字符串是由若干个t和一段字符x组成 如果没有x那么它就是一个周期串 并且x和t的开头是相同的 就是x是t的前缀

那么x的长度是多少呢 是n%t

既然x是t的前缀 就满意补上一些字符使x变成t 补多少字符呢 t-n%t , t= n-next[n]；

#include <cstdio>
#include <cstring>
const int maxn = 200010;
const int mod = 10007;
char a[maxn];
int f[maxn];
int dp[maxn];
int n, m;

void getFail()
{
	f[0] = f[1] = 0;
	for(int i = 1; i < n; i++)
	{
		int j = f[i];
		while(j && a[i] != a[j])
			j = f[j];
		f[i+1] = a[i] == a[j] ? j+1 : 0;
	}
	if(f[n] == 0)
	{
		printf("%d\n", n);
		return;
	}
	if(n%(n-f[n]) == 0)
	{
		printf("0\n");
		return;
	}
	printf("%d\n", n-f[n]-n%(n-f[n]));
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		m = 0;
		scanf("%s", a);
		n = strlen(a);
		getFail();
	}
	return 0;
}

HDU 3746 Cyclic Nacklace / KMP,布布扣,bubuko.com

HDU 3746 Cyclic Nacklace / KMP

原文：http://blog.csdn.net/u011686226/article/details/22052757