hdu 3336 Count the string(KMP)

题目链接：hdu 3336 Count the string

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

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

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