X和Y,当另一序列Z既是X的子序列又是Y的子序列时,若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。
同理,若序列Z既是X的子序列同时也是Y的子序列,则称Z为X和Y的公共子序列。其中最长的子序列称为最长公共子序列。
在求最长公共子序列中,我们可以看出如下规律:
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则
(1)若xm=yn,则zk=xm=yn,且zk-1是xm-1和yn-1的最长公共子序列。
(2)若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。(即:Z是X序列中前m个元素所组成的序列与Y序列的最长公共子序列)
(3)若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。(即:Z是Y序列中前n个元素所组成的序列与X序列的最长公共子序列)
由上面三个条件可得如下公式:
C[][]用来记录最长公共子序列的长度,则:
c[i][j] = <1> 0; (当i、j = 0时);
<2> c[i-1][j-1] + 1; (当i、j > 0 且 Xi = Yj时)(即第i个X序列元素与第j个Y元素相等)
<3> max(c[i][j-1] , c[i-1][j]) (当i、j > 0 且 Xi != Yj时)(当Xi与Yj不等时,取两个式子的最大值,若两者相等则默认取第一个)
/**
* 求出最大子序列的长度
* @param x 数组1
* @param y 数组2
* @param b 用于存放两个数组内容比较的情况
* @return 返回最大子序列的长度
*/
public static int lcsLength(String[] x, String[] y, int[][] b) {
int m = x.length - 1;
int n = y.length - 1;
int[][] c = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++){
c[i][0] = 0;
}
for (int i = 1; i <= n; i++)
c[0][i] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i].equals(y[j])) {
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
} else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 2;
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
return c[m][n];
}
/**
* 构造最长公共子序列
* @param i 第一个数组的长度
* @param j 第二个数组的长度
* @param x 两个数组中的一个
* @param b 记录了公共子序列情况的数组,该数组在lcs
*/
public static void lcs(int i, int j, String[] 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);
}
/**
* 初始化数组的方法
* @param str 要转化为数组的字符串
* @return 返回str转化成的数组
*/
private String[] init(String str){
String temp = str;
String[] s = temp.split("");
return s;
}
本来想将实现匹配公共子序列的矩阵的步骤的图贴上来的,但是不知道怎么用这个东西贴,真头疼....
main方法测试:
/**
* @param args
*/
public static void main(String[] args) {
String s1 = "ABCBDAB";
String s2 = "BDCABA";
CountMaxSerial cms = new CountMaxSerial();
String[] x = cms.init(s1);
String[] y = cms.init(s2);
int[][] b = new int[x.length][y.length];
System.out.println("最大子序列的长度为:"+lcsLength(x, y, b));
System.out.println("最大子序列为:");
lcs(x.length-1, y.length-1, x, b);
}
分享到:
相关推荐
C#实现-动态规划-最长公共子序列-DPLCS,根据动态规划的思想实现对最长公共子序列的求解。
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
只供参考,如有觉得不当的地方请指正! 当然这个问题还有很多种方法,但是我是理由动态分配内存来解决这个问题的,后面有delete来释放分配的内存单元。
C#-回溯-最长公共子序列-DCLCS;使用回溯的算法策略实现对最长公共子序列的求解。
利用动态规划 实现排序 找到最长公共工子序列
C++动态规划法实验源代码--最长公共子序列的源代码,很经典的。
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
算法与数据结构实验报告
动态规划解决最长公共子序列问题,即寻找两个序列中公共的序列中的最长的那个,结果不唯一,只能输出一个最长公共子序列,并不能生成所有的; 可视化多文档,手动输入两个子序列,显示动态规划算法的解决表格,箭头...
1. 要求按动态规划法原理求解问题; 2. 两个序列数据通过键盘输入; 3. 要求显示结果。
最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含问题的答案:找不到...
算法分析实验:动态规划法求最长公共子序列及其01背包
用Python实现动态规划中最长公共子序列和最长公共子串问题!
计算机算法设计与分析题目解答,最长公共子序列的动态规划解法
设序列X={x1,x2,…,xm}和Y={y1,y2,…,...(1)若xm=yn,则zk=xm=yn,且zk-1是xm-1和yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm,则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn,则Z是X和yn-1的最长公共子序列。
动态规划中的最长公共子序列PPT课件.pptx
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 ...(包括输入格式、算法、输出格式) ...(除了截图外,实验结果还用图表进行了分析) ...
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};
(一)本题随着序列的更新,最长公共子序列的变化具有前效性,符合动态规划的特点,自然想到动态规划的方法。 (二)a字符串每增加一个字符ai,都将它和b中的所有字符比较一遍,如果遇到相等的那么当前的最长公共子...
这是用动态规划算法求解给定的两个序列的最长公共子序列的C++程序。