最长公共子序列LCS
2023-03-14 10:17:26 时间
时间限制:1 秒 空间限制:65536 KB 分值: 0 给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。 比如两个串为: abcicba abdkscab ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。 Input 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) Output 输出最长的子序列,如果有多个,随意输出1个。 Input 示例 abcicba abdkscab Output 示例 abca
动态规划的一个计算两个序列的最长公共子序列的方法如下:
以两个序列 X、Y 为例子:
设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。
此时,二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char str1[1002],str2[1002]; int d[1002][1002]; int main() { while(gets(str1) && gets(str2)) { int len1=strlen(str1),len2=strlen(str2); memset(d,0,sizeof(d)); for(int i=len1-1; i>=0; i--) for(int j=len2-1; j>=0; j--) { if(str1[i]==str2[j]) d[i][j]=d[i+1][j+1]+1; else d[i][j]=max(d[i+1][j],d[i][j+1]); } int i = 0, j = 0; while (i < len1 && j < len2){ if (str1[i] == str2[j]){ printf("%c",str1[i]); i++; j++; } else if (d[i+1][j] >= d[i][j+1]) i++; else j++; } printf("\n"); } return 0; }
相关文章
- 在 Amazon SageMaker notebook 实例上使用 R 编程
- AWS Content Analysis 解决方案介绍
- 教育网站 ApplyBoard 使用 CloudWatch Container Insights 监控关键任务 EKS 环境
- TUNA 开源镜像站分站在由西云数据运营的 AWS 中国(宁夏)区域上正式上线并开放服务
- 宣布在洛杉矶推出第二个本地区域
- Python Tkinter 之Frame控件(Python GUI 系列4)
- 轻松便捷为 AWS WAF 部署一套仪表板
- 将 Linux 实例无缝加入适用于 Microsoft Active Directory 的 AWS Directory Service 中
- 使用 Route 53 解析器查询日志记录您的 VPC DNS 查询
- 使用 AWS Transcribe 配合物联网设备构建一套支持多语种的语音到文本通知系统
- 在 Amazon EMR 上监控 Spark Streaming 应用程序
- 使用应用程序负载均衡器在私有子网内安全访问 Amazon EMR Web 接口
- 在 Amazon EMR 上使用 Dr. Elephant 与 Sparklens 实现 Hadoop 与 Spark 性能调优
- Bottlerocket:一套专用型容器操作系统
- 开发者指南:当 Amazon EFS 遇上 Amazon ECS 与 AWS Fargate——第一部分
- 聊聊 AWS Fargate 在容器世界中的角色定位
- 新 EBS 卷类型 (io2) — 耐用性提高 100 倍,IOPS/GiB 提高 10 倍
- 在 EMR 6.0.0 上利用 Hive LLAP 实现 Apache Hive 性能倍增
- Wind Mobility 公司如何构建无服务器数据架构
- Announcing the newest AWS Heroes – August 2020