本文共 961 字，大约阅读时间需要 3 分钟。

链接：

题目大意：

给一个字符串，求出这个字符串的所有前缀出现的次数之和。

分析与总结：

运用到了dp的思想，dp弱逼一个表示压力很大。。。

向这位博主大人学习了：

找出前缀后，算出现次数，很明显的是一个单模式串匹配问题，KMP 可以很好的解决，不过如果直接这样暴力的话，O(n^2) 的复杂度还是不行的。。。因此，我们试着考虑 KMP 算法进行快速匹配的本质核心所在，其实就是 next[] 数组

而这个的本质其实就是 S[1..next[i]]=S[i-next[i]+1...i] 

即模式串的最长公共前后缀串的长度

举个例子 ababa 

我们要算这个字符串的前缀的出现次数和

a 出现 3 

ab 出现 2

aba 出现 2

abab 出现 1

ababa 出现 1

那么我们可以这样来 DP 

记 dp[i] 为前 i 个字符组成的前缀出现的次数

则 dp[next[i]]+=dp[i] 

这个转移方程是什么含义呢？？？

我们可以这样来想

如 dp[3] 对应 aba 且 next[5]=3

则 dp[3]+=dp[5] 为答案

因为  S[1..next[i]]=S[i-next[i]+1...i]  aba 自己出现了 dp[3] ，然后 S[i-next[i]+1..i] 出现了 dp[5] 也是 aba 会出现的地方，因此也要加上

（还是要自己 YY 一下，这里说不清啊）

初始化的时候，记得 dp[i]=1 表示自身匹配算 1 次

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int MAXN = 200005;const int MOD  = 10007;char T[MAXN];int  f[MAXN];int  dp[MAXN];int n;int getFail(char* p,int* f){    int n=strlen(p);    f[0]=f[1]=0;    dp[0] = 1;    int ans=1;    for(int i=1; i
     
    
   

          原创  ， By   D_Double  (转载请标明)