HUST 1328 String KMP 递增思路

题意：求各个前缀在字符串中的出现的个数和。

KMP匹配一次的复杂度是0(n)，这题如果暴力查找前缀进行KMP匹配的话，果断会跪。

其实这题又是一题next数组的应用。

我们可以递推，每次仅仅看前i个字符，看看它的增加会影响到多少个匹配，很明显，next[i]能影响的它也能影响，而它又影响自己本身。这样就能解出来了。

非常蛋疼地送了几个WA 了long long...

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        hust1328.cpp
*  Create Date: 2013-12-01 18:21:18
*  Descripton:  kmp 
*/

#include 
   
     #include 
    
      const int MAXN = 1e5 + 1; int f[MAXN], ans[MAXN]; // 分别是next数组和记录影响数的数组 char P[MAXN]; void getVal(int l) { int i = 0, j = -1; f[0] = -1; while (i < l) { if (j == -1 || P[i] == P[j]) { i++; j++; f[i] = j; } else j = f[j]; } f[0] = 0; } int main() { int t; scanf("%d\n", &t); while (t--) { gets(P); int len = strlen(P); getVal(len); // KMP long long cnt = 0; memset(ans, 0, sizeof(ans)); for (int i = 1; i <= len; i++) { ans[i] = ans[f[i]]; // 这个字符的增加使得多少个字符也增加了 ans[i]++; // 这个字符也影响本身 cnt += ans[i]; } printf("%lld\n", cnt); } return 0; }