信息学奥赛一本通 1265:最长公共子序列(evd)
发布日期:2022-01-30 02:41:38
浏览次数:25
分类:技术文章
本文共 1192 字,大约阅读时间需要 3 分钟。
【题目描述】
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1,x2,…,xm>,则另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有:Xij=Zj
例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>,则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列.因为X和Y没有长度大于4的公共子序列。给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2….yn>.要求找出X和Y的一个最长公共子序列。
【输入】
共有两行。每行为一个由大写字母构成的长度不超过1000的字符串,表示序列X和Y。【输出】
第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列.则输出文件仅有一行输出一个整数0。【输入样例】
ABCBDAB BDCABA 【输出样例】 4 【提示】 最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,LCS)的区别为:子串是串的一个连续的部分,子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。字符串长度小于等于1000。 【心得】能理解边界的意义就够了,输出的是f[len1][len2],但比较的是[0,len1-1]和[0,len2-1]。 【AC代码】#include#include #include using namespace std;const int N=5005;int f[N][N];char s1[N],s2[N];int main(){ scanf("%s\n%s",s1,s2); int len1,len2; len1=strlen(s1);len2=strlen(s2); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(s1[i-1]==s2[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } } cout<
转载地址:https://blog.csdn.net/everwide1982/article/details/109837694 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月04日 13时39分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ubuntu 上cuda安装出现的一些问题
2019-04-27
大公司的高薪 OR 创业公司的期权,更加看中大公司的高薪?
2019-04-27
keil MDK使用虚拟示波器
2019-04-27
沟通中的各种障碍
2019-04-27
未来五年,不懂人工智能的程序员不会被淘汰
2019-04-27
onvif摄像头发现设备
2019-04-27
Android的页面跳转
2019-04-27
STM32adc采集的一些bug
2019-04-27
嵌入式的系统休眠
2019-04-27
μCosII的体系结构
2019-04-27
windows下链接mysql数据库
2019-04-27
C#窗体程序
2019-04-27
C#计算
2019-04-27
C#的groupbox和字体修改
2019-04-27
C#checkbox使用
2019-04-27
C# 改进checkbox使用
2019-04-27
C#下面的listbox使用
2019-04-27
C# combobox使用
2019-04-27
C# linklabel使用
2019-04-27
C# timer添加事件处理
2019-04-27