题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5763
题意:给定两个字符串a和b,其中a中的字符串如果含有子串b,那么那部分可以被替换成*。问有多少种替换方法。
kmp求出b在a中完全匹配后的结尾位置,然后dp(i)表示匹配到i时替换的方案数(不替换也算一次方案)。首先更新dp(i)=dp(i-1),当且仅当i点是一个完全匹配的终点时,加上dp(i-nb)处的值。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
const int mod = ;
int na, nb;
char a[maxn];
char b[maxn];
int pre[maxn];
bool vis[maxn];
int dp[maxn]; void getpre(char *b, int *pre) {
int j, k;
pre[] = -;
j = ;
k = -;
while(j < nb) {
if(k == - || b[j] == b[k]) {
j++;
k++;
pre[j] = k;
if(b[j] != b[k]) pre[j] = k;
else pre[j] = pre[k];
}
else k = pre[k];
}
} void kmp() {
int i = ;
int j = ;
getpre(b, pre);
while(i < na) {
if(j == - || a[i] == b[j]) {
i++; j++;
}
else j = pre[j];
if(j == nb) vis[i] = ;
}
} int main() {
// freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
printf("Case #%d: ", _++);
scanf("%s %s", a, b);
memset(vis, , sizeof(vis));
memset(dp, , sizeof(dp));
na = strlen(a); nb = strlen(b);
kmp(); dp[] = ;
for(int i = ; i <= na; i++) {
dp[i] = dp[i-];
if(vis[i]) {
dp[i] += dp[i-nb];
dp[i] %= mod;
}
}
printf("%d\n", dp[na]%mod);
}
return ;
}
[HDOJ5763]Another Meaning(KMP, DP)的更多相关文章
-
HDU 5763 Another Meaning (kmp + dp)
Another Meaning 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5763 Description As is known to all, ...
-
HDU5763 another meaning -(KMP+DP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5763 思路:dp[i]表示前i个字符组成的字符串所表示的意思数量,则当匹配时dp[i]=dp[i-1] ...
-
hdu_3336: Count the string(KMP dp)
题目链接 题意:求给定字符串中,可以与某一前缀相同的所有子串的数量 做这道题需要明白KMP算法里next[]数组的意义 首先用一数组nex[](这里与之前博客中提到的next明显不同)存储前缀后缀最长 ...
-
hdu 3336 count the string(KMP+dp)
题意: 求给定字符串,包含的其前缀的数量. 分析: 就是求所有前缀在字符串出现的次数的和,可以用KMP的性质,以j结尾的串包含的串的数量,就是next[j]结尾串包含前缀的数量再加上自身是前缀,dp[ ...
-
hdu3689(kmp+dp)
题意:问随机生成一个长度为m(m<=1000)长度的字符串,出现某个子串s的概率是多少. 解法:dp+kmp优化.ans[i][j]表示i长度,走到了s的j位置的概率,当然这是在i之前没有出现s ...
-
【HDU 3336】Count the string(KMP+DP)
Problem Description It is well known that AekdyCoin is good at string problems as well as number the ...
-
hdu 6068--Classic Quotation(kmp+DP)
题目链接 Problem Description When online chatting, we can save what somebody said to form his ''Classic ...
-
HDU3336(KMP + dp)
Count the string Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) ...
-
2019.03.01 bzoj3075: [Usaco2013]Necklace(kmp+dp)
传送门 题意简述:给出S,TS,TS,T两个字串,∣S∣≤10000,∣T∣≤1000|S|\le10000,|T|\le1000∣S∣≤10000,∣T∣≤1000,问至少从SSS中删去几个字符能够 ...
随机推荐
-
cellery ImportError &; AttributeError
一.zz的问题 celery 运行work要进入到 文件所在的文件夹下执行 二.AttributeError: 'Flask' object has no attribute 'user_option ...
-
IOS AVAUDIOPLAYER 播放器使用
1. 导入 AVFoundation.framework 2.导入头文件 #import <AVFoundation/AVFoundation.h> 3. player = [[AVAu ...
-
thinkphp 3.2.3 入门示例2(URL传参数的几种方式)
原文:thinkphp中URL传参数的几种方式 在thinkphp中,url传参合asp.net中原理类似,下面就单个参数和多个参数传递方式进行一个简单讲解 1.传单个参数 单个参数这种比较简单,例如 ...
-
tomcat 下部署单框架cas时,报出org.apache.jasper.JasperException异常的解决办法
在tomcat中部署好cas server(设置好https,将cas.war拷贝到了webapps下部署完成),启动tomcat后,访问http://localhost:8443/cas/login ...
-
如何用php实现简单的文件上传功能?(带图解)
如图所示:点击浏览出现选择文件的对话框,将所选文件上传到保存文件的文件. 关键点:文件上传的图解: 代码: <!DOCTYPE html> <html> <head&g ...
-
【RegExp】JavaScript中正则表达式判断匹配规则以及常用方法
字符串是编程时涉及到的最多的一种数据结构,对字符串进行操作的需求几乎无处不在. 正则表达式是一种用来匹配字符串的强有力的武器.它的设计思想是用一种描述性的语言来给字符串定义一个规则,凡是符合规则的字符 ...
-
Python基础(文件操作)
文件读取: #文件读取方式一 f=open("a.txt","r+",encoding="utf8") data=f.read() prin ...
-
事务、事务特性、事务隔离级别、spring事务传播特性
事务.事务特性.事务隔离级别.spring事务传播特性 1.什么是事务: 事务是程序中一系列严密的操作,所有操作执行必须成功完成,否则在每个操作所做的更改将会被撤销,这也是事务的原子性(要么成功, ...
-
dbms_sqltune.report_sql_monitor 自动调优
--创建 dbms_sqltune.create_tuning_task ; --执行 dbms_sqltune.execute_tuning_task; --产看创建的task 和 status S ...
-
Vue如何循环渲染图片
Vue如何把服务器返回的图片数据渲染出来 首先,一般来说,当请求图片的接口时,会返回一个数组,这个数组里会是一些图片的名字,比如1.jpg,2.jpg. 我的做法是先在data里定义一个数组,来存储服 ...