[HDOJ5763]Another Meaning(KMP, DP)

时间:2022-09-05 13:08:15

题目链接: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)的更多相关文章

  1. HDU 5763 Another Meaning (kmp &plus; dp)

    Another Meaning 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5763 Description As is known to all, ...

  2. HDU5763 another meaning -(KMP&plus;DP)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5763 思路:dp[i]表示前i个字符组成的字符串所表示的意思数量,则当匹配时dp[i]=dp[i-1] ...

  3. hdu&lowbar;3336&colon; Count the string(KMP dp)

    题目链接 题意:求给定字符串中,可以与某一前缀相同的所有子串的数量 做这道题需要明白KMP算法里next[]数组的意义 首先用一数组nex[](这里与之前博客中提到的next明显不同)存储前缀后缀最长 ...

  4. hdu 3336 count the string(KMP&plus;dp)

    题意: 求给定字符串,包含的其前缀的数量. 分析: 就是求所有前缀在字符串出现的次数的和,可以用KMP的性质,以j结尾的串包含的串的数量,就是next[j]结尾串包含前缀的数量再加上自身是前缀,dp[ ...

  5. hdu3689(kmp&plus;dp)

    题意:问随机生成一个长度为m(m<=1000)长度的字符串,出现某个子串s的概率是多少. 解法:dp+kmp优化.ans[i][j]表示i长度,走到了s的j位置的概率,当然这是在i之前没有出现s ...

  6. 【HDU 3336】Count the string(KMP&plus;DP)

    Problem Description It is well known that AekdyCoin is good at string problems as well as number the ...

  7. hdu 6068--Classic Quotation(kmp&plus;DP)

    题目链接 Problem Description When online chatting, we can save what somebody said to form his ''Classic ...

  8. HDU3336(KMP &plus; dp)

    Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  9. 2019&period;03&period;01 bzoj3075&colon; &lbrack;Usaco2013&rsqb;Necklace(kmp&plus;dp)

    传送门 题意简述:给出S,TS,TS,T两个字串,∣S∣≤10000,∣T∣≤1000|S|\le10000,|T|\le1000∣S∣≤10000,∣T∣≤1000,问至少从SSS中删去几个字符能够 ...

随机推荐

  1. cellery ImportError &amp&semi; AttributeError

    一.zz的问题 celery 运行work要进入到 文件所在的文件夹下执行 二.AttributeError: 'Flask' object has no attribute 'user_option ...

  2. IOS AVAUDIOPLAYER 播放器使用

    1. 导入 AVFoundation.framework 2.导入头文件  #import <AVFoundation/AVFoundation.h> 3. player = [[AVAu ...

  3. thinkphp 3&period;2&period;3 入门示例2&lpar;URL传参数的几种方式&rpar;

    原文:thinkphp中URL传参数的几种方式 在thinkphp中,url传参合asp.net中原理类似,下面就单个参数和多个参数传递方式进行一个简单讲解 1.传单个参数 单个参数这种比较简单,例如 ...

  4. tomcat 下部署单框架cas时,报出org&period;apache&period;jasper&period;JasperException异常的解决办法

    在tomcat中部署好cas server(设置好https,将cas.war拷贝到了webapps下部署完成),启动tomcat后,访问http://localhost:8443/cas/login ...

  5. 如何用php实现简单的文件上传功能?(带图解)

    如图所示:点击浏览出现选择文件的对话框,将所选文件上传到保存文件的文件.  关键点:文件上传的图解: 代码: <!DOCTYPE html> <html> <head&g ...

  6. 【RegExp】JavaScript中正则表达式判断匹配规则以及常用方法

    字符串是编程时涉及到的最多的一种数据结构,对字符串进行操作的需求几乎无处不在. 正则表达式是一种用来匹配字符串的强有力的武器.它的设计思想是用一种描述性的语言来给字符串定义一个规则,凡是符合规则的字符 ...

  7. Python基础(文件操作)

    文件读取: #文件读取方式一 f=open("a.txt","r+",encoding="utf8") data=f.read() prin ...

  8. 事务、事务特性、事务隔离级别、spring事务传播特性

    事务.事务特性.事务隔离级别.spring事务传播特性   1.什么是事务: 事务是程序中一系列严密的操作,所有操作执行必须成功完成,否则在每个操作所做的更改将会被撤销,这也是事务的原子性(要么成功, ...

  9. dbms&lowbar;sqltune&period;report&lowbar;sql&lowbar;monitor 自动调优

    --创建 dbms_sqltune.create_tuning_task ; --执行 dbms_sqltune.execute_tuning_task; --产看创建的task 和 status S ...

  10. Vue如何循环渲染图片

    Vue如何把服务器返回的图片数据渲染出来 首先,一般来说,当请求图片的接口时,会返回一个数组,这个数组里会是一些图片的名字,比如1.jpg,2.jpg. 我的做法是先在data里定义一个数组,来存储服 ...