本文主要是介绍HDU 3336 Count the string(经典，KMP+DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3336
题目大意：
给一个字符串，求出这个字符串的所有前缀出现的次数之和。
分析与总结：
运用到了dp的思想，dp弱逼一个表示压力很大。。。
向这位博主大人学习了：http://www.cnblogs.com/yuelingzhi/archive/2011/08/03/2126346.html
找出前缀后，算出现次数，很明显的是一个单模式串匹配问题，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<iostream>
#include<cstdio>
#include<cstring>
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<n; ++i){int j=f[i];while(j && p[i]!=p[j]) j=f[j];f[i+1] = p[i]==p[j]?1+j:0;}return ans;
}int main(){int nCase;scanf("%d",&nCase);while(nCase--){scanf("%d",&n);scanf("%s",T);getFail(T,f);int sum=0;int len=strlen(T);memset(dp, 0, sizeof(dp));for(int i=1; i<=n; ++i){dp[i] = (dp[f[i]]+1) %MOD;sum = (sum+dp[i])%MOD;}printf("%d\n",sum);}return 0;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于HDU 3336 Count the string(经典，KMP+DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
