hdu4681--String
发布日期:2022-02-02 02:58:06 浏览次数:15 分类:技术文章

本文共 1784 字,大约阅读时间需要 5 分钟。

Problem Description
Given 3 strings A, B, C, find the longest string D which satisfy the following rules:
a) D is the subsequence of A
b) D is the subsequence of B
c) C is the substring of D
Substring here means a consecutive subsequnce.
You need to output the length of D.
 

Input
The first line of the input contains an integer T(T = 20) which means the number of test cases.
For each test case, the first line only contains string A, the second line only contains string B, and the third only contains string C.
The length of each string will not exceed 1000, and string C should always be the subsequence of string A and string B.
All the letters in each string are in lowercase.
 

Output
For each test case, output Case #a: b. Here a means the number of case, and b means the length of D.
 

Sample Input
2aaaaaaaaa aaabcdefacebdfcf
 

Sample Output
Case #1: 4Case #2: 3   
Hint
For test one, D is "aaaa", and for test two, D is "acf".

                             D是A的子序列,也是B的子序列,C是D的子串

先找出A和B的最长公共子序列,然后再把A和B倒过来,求其最长公共子序列。最后把C的头和尾分别在A和B中标记下来,然后求之。

代码实现:

#include
#include
#include
#define M 1007using namespace std;int dp1[M][M],dp2[M][M];char s1[M],s2[M],s3[M],st1[M],st2[M];int z1[M][2],z2[M][2];int len1,len2,len3;int main(){ int t; cin>>t; for(int cas=1; cas<=t; cas++) { cin>>s1>>s2>>s3; len1=strlen(s1); len2=strlen(s2); len3=strlen(s3); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); //dp1[][]求的是s1和s2的最大公共子序列 for(int i=1; i<=len1; i++) for(int j=1; j<=len2; j++) if(s1[i-1]==s2[j-1]) dp1[i][j]=dp1[i-1][j-1]+1; else dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]); //st1是将s1字符串转过来 for(int i=0; i

转载地址:https://blog.csdn.net/u010368749/article/details/18620195 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:求最长公共子序列
下一篇:动态规划---hdu--1421 搬寝室

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月09日 04时07分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python画多层网络_在pymn中修改多层网络图 2019-04-21
java net 安卓_android -------- java.net.UnknownServiceException 2019-04-21
java 密钥 aes 解密_Java中AES加密解密以及签名校验 2019-04-21
java树转化成图_Java 转换一组数据为树型数据 2019-04-21
java 底层ppt_Java 如何设置 PPT 中的形状排列方式 具体内容 2019-04-21
mysql更新第5条记录_MYSQL中添加、更新、删除数据 2019-04-21
mysql service5.7_Mysql5.7服务下载安装 2019-04-21
mysql查看线程完整执行命令_MySQL-查看运行的线程-SHOW PROCESSLIST 2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串 2019-04-21
web开发 mysql安装_mysqlinstallerwebcommunity5.7.21.0.msi安装图文教程 2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast) 2019-04-21
mysql单元格函数是_MySQL常用内置函数 2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗? 2019-04-21
mysql server卸载出错_Mysql卸载问题Start Server卡住报错解决方法 2019-04-21
全国省市区 mysql_2017全国省市区数据库【含三款数据库】 2019-04-21
druid加载MySQL驱动原理_你好,想知道mybatis+druid+jdbc 原理介绍? 2019-04-21
mysql 怎样链接jdbc_jdbc怎么链接mysql数据库 2019-04-21
mysql学生课程表试题_Mysql练习之 学生表、课程表 、教师表、成绩表 50道练习题... 2019-04-21
java exec封装_Java 执行系统命令工具类(commons-exec) 2019-04-21
php sha512解密,PHP加密函数 sha256 sha512 sha256_file() sha512_file() 2019-04-21