hdu 3746 Cyclic Nacklace(KMP)

题目链接：hdu 3746 Cyclic Nacklace

题目大意：问说最少需要在添加几个值，可以是字符串变成以一个子字符串循环得到的（至少有两个该子串）

解题思路：KMP的变形吧，将字符串的next数组求出来，next[n]是关键；k = n - next[n]，如果k = 0的话，说明没有一个匹配的字符，那么至少就要添加n个；n%k = 0的话，说明该字符串已经满足了要求，不需要添加；如果n%k!=0的话，那么久的计算说要添加几个，k - (n-（n/k)*k).

#include <stdio.h>
#include <string.h>

const int N = 1e5+5;

int n, next[N];
char str[N];

void getNext () {
	n = strlen (str+1);
	int p = 0;
	for (int i = 2; i <= n; i++) {
		while (p > 0 && str[p+1] != str[i])
			p = next[p];

		if (str[p+1] == str[i])
			p++;
		next[i] = p;
	}
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		scanf("%s", str+1);
		getNext();

		if (next[n] == 0) printf("%d\n", n);
		else {
			int k = n - next[n];
			if (n%k == 0) printf("0\n");
			else printf("%d\n", k - (n - (n/k) * k));
		}
	}
	return 0;
}

hdu 3746 Cyclic Nacklace(KMP),布布扣,bubuko.com

hdu 3746 Cyclic Nacklace(KMP)

原文：http://blog.csdn.net/keshuai19940722/article/details/21403723