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 
#include 

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;
}