最长公共子序列(LCS)
最长公共子序列(LCS)
- 0、写在前面
- 1、问题描述
- 2、最长公共子序列的结构
- 3、子问题的递归结构
- 4、计算最优值
- 5、算法的改进
- 6、参考
0、写在前面
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xi,j。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列
。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列
。
1、问题描述
给定序列 X=<x1, x2, … , xm>, Y=<y1, y2, … , yn>,求 X 和 Y 的最长公共子序列
- 实例:
X: A B C B D A B Y: B D C A B A 一个最长公共子序列: B C B A
蛮力算法:检查 X 的每个子序列在Y 中出现每个子序列 O(n) 时间,X 有 2m 个 子序列,最坏情况下时间复杂度:O(n·2m)
2、最长公共子序列的结构
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则
- 若xm=yn,则zk=xm=yn,且zk-1是xm-1和yn-1的最长公共子序列。
- 若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。
- 若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。
3、子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下,由最优子结构性质可建立递归关系如下:
标记函数:B[i, j], 其值为字符↖(1)、⬅ (3)、⬆(2),分别表示C[i,j]取得最大值时的三种情况
4、计算最优值
由于在所考虑的子问题空间中,总共有θ(mn)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。
- 计算最长公共子序列的长度
Algorithm lcsLength(x,y,b)
1:m<--x.length;
2:n<--y.length;
3:c[i][0]=0; c[0][i]=0;
4:for (int i= 1; i <= m; i++)
5: for (int j = 1; j <= n; j++)
6: if (x[i]==y[j])
7: c[i][j]=c[i-1][j-1]+1;
8: b[i][j]=1; ↖
9: else if (c[i-1][j]>=c[i][j-1])
10: c[i][j]=c[i-1][j];
11: b[i][j]=2; ⬆
12: else
13: c[i][j]=c[i][j-1];
14: b[i][j]=3; ⬇
- 构造最长公共子序列
Algorithm lcs(int i,int j,char [] x,int [][] b) {
if (i ==0 || j==0) return;
if (b[i][j]== 1 ↖ ){
lcs(i-1,j-1,x,b);
System.out.print(x[i]);
}
else if (b[i][j]== 2 ) lcs(i-1,j,x,b);
else lcs(i,j-1,x,b);
}
示例
- 输入:
X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>,
- 结果函数:Cij
- 解:长度为4
实例
5、算法的改进
- 在算法lcsLength和lcs中,可进一步将数组b省去。事实上,数组元素c[i][j]的值仅由c[i-1][j-1],c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j],可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1],c[i-1][j]和c[i][j-1]中哪一个值所确定的。
- 如果只需要计算最长公共子序列的长度,则算法的空间需求可大大减少。事实上,在计算c[i][j]时,只用到数组c的第i行和第i-1行。因此,用2行的数组空间就可以计算出最长公共子序列的长度。
- 进一步的分析还可将空间需求减至O(min(m,n))。
6、参考
- 算法设计与分析(第4版)
结束!
相关文章
- 当大数据平台遇到K8s,智领云助力企业向数据驱动转型
- 研究研究 ES_OEMCONVERT 标志,你学会了吗?
- ISO 镜像已放出,Linux Mint 21.1 Beta 版本上线
- 事件循环机制:JavaScript被设计为单线程,那如何做到异步的呢?
- 微软 Windows 10 / Windows 11 免费工具集 PowerToys 0.65.0 发布:兼容 .NET 7
- 你需要知道的 TCP 三次握手
- Linux 系统日志—Secure,Btmp,Wtmp文件详解
- Bash 初学者系列 5:在 bash 中进行数学运算
- 已置顶横条通知,谷歌 Chrome 浏览器不再支持 Windows 7 / Windows 8.1 平台
- 2022数博会:把脉工业互联网发展之道
- Trinity 桌面环境 R14.0.13 版发布更新
- 用 Lua 解析参数
- 大数据技术的成功案例及趋势
- 实施合理的数据收集策略的重要性
- DevOps 的运营和商业利益指南
- 如何避免淹没在云原生可观测性数据中
- 如何免费激活 Windows 11 系统?Windows 7密钥是个不错的选择
- Microsoft Edge 108 稳定版发布,支持启用 TLS ECH 加密
- 如何在 Bash 脚本中分割字符串
- Mozilla 正开发 Firefox 浏览器特定站点的搜索功能,可一步到位显示搜索结果