最长公共子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:3
tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.
2 asdf adfsd 123abc abc123abc
3 6
思路:
如图所示为最长公共子序列。(子序列是不连续的,子串是连续的)
现有两个序列X={x1,x2,x3,...xi},Y={y1,y2,y3,....,yi},
设有C[i,j]: 保存Xi与Yj的最长公共子序列(LFS)的长度。
演示过程如图所示,如果Xi,Yi相同,则取对角线的数+1;
如果Xi,Yi不相同,则对比上面或左边的数,取最大值+1;
根据下面的演示其实可以发现C[i,j]一直保存着当前(Xi,Yi)的最大子序列长度。
(1) 当X[i]=Y[j]时, C(i, j)=C(i-1, j-1) 1 。证明很简单。
(2) 当X[i]!=Y[j]时, 说明此事X[0...i]和Y[0...j]的最长公共子序列中绝对不可能同时含有X[i]和Y[j]。那么公共子序列可能以X[i]结尾,可能以Y[j]结尾,可以末尾都不含有X[i]或Y[j]。
因此 C(i, j)= MAX{Ci-1 , j), C(i, j-1)}
Explain in detail:
事实上,最长公共子序列问题也有最优子结构性质。
记:
Xi = <x1,x2,x3,....xi> 即X序列的前i个字符(1<= i <= m)(前缀)
Yj = <y1,y2,y3,....yi> 即Y序列的前j个字符(1<= j <= m)(前缀)
假定Z = <z1,z2,z3,...zk>是LCS(X,Y)中的一个。
·若xm = yn(最后一个字符相同),则不难用反正法证明:该字符必是X与Y的任一最长公共子序列Z(设长度为k)的最后一个字符,即有zk = xm = yn,且显然有Zk-1∈LCS(Xm-1,Yn-1),即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X,Y))的长度等于LCS(Xm-1,Yn-1)的长度加1)。
·若xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm-1, Y),要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1 , Y);类似的,若zk≠yn 则有Z∈LCS(X , Yn-1)。此时,问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。
由于上述当xm≠yn的情况中,求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度,这两个问题不是相互独立的:两者都需要求LCS(Xm-1,Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。
Wrong:
#include<stdio.h> #include<string.h> int main() { int N,i,j; int alen,blen; char a[1005]; char b[1005]; char same[1005][1005]; //手抽这里写错了 应该是int类型…… scanf("%d",&N); while(N--) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(same,0,sizeof(same)); scanf("%s",a); scanf("%s",b); alen=strlen(a); blen=strlen(b); for(i=1;i<=alen;i++) for(j=1;j<=blen;j++) { if(a[i-1]==b[j-1]) same[i][j]=same[i-1][j-1]+1; //这里的字符要-1 else same[i][j]=(same[i-1][j]>same[i][j-1]?same[i-1][j]:same[i][j-1]); } printf("%d\n",same[alen][blen]); } return 0; }
AC:
#include<stdio.h> #include<string.h> int main() { int N,i,j; int alen,blen; char a[1005]; char b[1005]; int same[1005][1005]; scanf("%d",&N); while(N--) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(same,0,sizeof(same)); scanf("%s",a); scanf("%s",b); alen=strlen(a); blen=strlen(b); for(i=1;i<=alen;i++) for(j=1;j<=blen;j++) { if(a[i-1]==b[j-1]) same[i][j]=same[i-1][j-1]+1; else same[i][j]=(same[i-1][j]>same[i][j-1]?same[i-1][j]:same[i][j-1]); } printf("%d\n",same[alen][blen]); } return 0; }
总结:
吸收一下别人的解法。要静下心来慢慢理解。
相关推荐
计算机算法设计与分析题目解答,最长公共子序列的动态规划解法
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
最长公共子序列问题,用C#实现的动态规划算法 X=ABCBDAB Y=BDCABA 以上是示例用的测试数据,输入数据可以得到结果
动态规划的经典问题,求两个序列的最长公共子序列
程序以输出正确的结果大家不要费心去修改,用c++编写
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
算法设计-最长公共子序列动态规划算法.doc
动态规划解决最长公共子序列问题,即寻找两个序列中公共的序列中的最长的那个,结果不唯一,只能输出一个最长公共子序列,并不能生成所有的; 可视化多文档,手动输入两个子序列,显示动态规划算法的解决表格,箭头...
最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含问题的答案:找不到...
动态规划中的最长公共子序列PPT课件.pptx
最长公共子序列(lcs)使用动态规划解决采用c++编写
利用动态规划 实现排序 找到最长公共工子序列
算法导论实验:动态规划实现最长公共子序列问题,python实现; KR算法c语言实现。 附实验报告以及相关KMP算法的调研。
用c++实现最长公共子序列,实验课程作业,绝对可以运行。
最长公共子序列,动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法
一个最长公共子序列算法的试验报告,挺全的,传上来给大家分享
用Python实现动态规划中最长公共子序列和最长公共子串问题!
1. 要求按动态规划法原理求解问题; 2. 两个序列数据通过键盘输入; 3. 要求显示结果。
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS 1.实现基于优化子结构的递归求解算法 2.实现基于动态规划的求解算法 3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所...