hdu 3336 Count the string(KMP)

题目链接：hdu 3336 Count the string

题目大意：给出一个字符串，要求计算所有前缀串在该字符串中出现次数的总和。

解题思路：首先求出jump数组，然后对于每个位置来说，如果jump[p]!=0的话，即为存在一个前缀串，注意这里p = jump[p]， 因为前缀串中含可能包含前缀串。最后要+n。

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

const int N = 1e5+5;
const int MOD = 10007;

int n, jump[N*2];
char s[N*2];

int getCnt (int p) {
	int ans = 0;
	while (p) {
		ans++;
		p = jump[p];
	}
	return ans;
}

int getJump () {
	int p = 0, ans = n % MOD;

	for (int i = 2; i <= n; i++) {
		while (p > 0 && s[p+1] != s[i])
			p = jump[p];

		if (s[p+1] == s[i])
			p++;

		jump[i] = p;
		ans = (ans + getCnt(p)) % MOD;
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		scanf("%d%s", &n, s+1);
		printf("%d\n", getJump());
	}
	return 0;
}