链接:
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-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
HDU的一题........HDU DP动态规
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
ACM题库,一些题目和答案,以及解题报告,传上来共享
动态规划DP题解 POJ HDU部分动态规划DP题解
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
HDU图论题目分类
hdu 1574 passed sorce
hdu2101AC代码