最长公共子序列(动态规划解决)
其中:某个序列的子序列定义为原序列中的0个或多个元素被去掉之后剩下的元素序列。
给定两个序列
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 }
最长公共子序列为
LSC = { b , c , b , a }
分析:
最长公共子序列问题具有最优子结构性质
设
X = { x1 , … , xm }
Y = { y1 , … , yn }
及它们的最长子序列
Z = { z1 , … , zk }
则
1、若 xm = yn , 则 zk = xm = yn,且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列
2、若 xm != yn ,且 zk != xm ,
则 Z 是 X[m-1] 和 Y 的最长公共子序列
3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列
定义c[i,j]为序列Xi和Yj的最长公共子序列的长度,由性质导出子问题的递归结构
当 i = 0 , j =
0 时 , c[i][j] = 0
当 i , j >
0 ; xi = yi 时 , c[i][j] =
c[i-1][j-1] + 1
当 i , j >
0 ; xi != yi 时 , c[i][j] =
max { c[i][j-1] , c[i-1][j] }
在这个公式的基础上不难得到一个指数复杂度的递归算法求最长公共子序列,但是考虑到对长度分别为m, n的序列X, Y,其前缀分别有m+1, n+1个,不同的子问题个数的最多有(m+1)(n+1)个,可以用动态规划法自底向上求解。算法是:
对给定的xm , yn
1、如果m=0或者n=0,返回0,算法结束。
2、建立数组c[m+1][n+1],将c[0][0..n],
c[0..m][0]初始化为0。[注:c[i][j]在i=0或j=0时取值为0。]
3、按照从左到右,从上到下的顺序填表。对c[i][j]来说,如果xi=yj,那么令delta=1,
c[i][j]的值是以下三者中最大的一个:c[i-1][j], c[i][j-1], c[i-1][j-1]+delta。
4、表c填满后,c[m][n]的值就是最大公共子序列的长度。
5、填表过程结束后,按照第3步的规则倒推,即可知道哪些i,
j的值是出现在最长公共子序列中的下标。
代码如下:
String mStr1 = "abefcadasda";
String mStr2 = "abkcefaasd";
// 公共子序列长度
int[][] mLength = new int[mStr1.length() + 1][mStr2.length() + 1];
//路径
String[][] mPath = new String[mStr1.length() + 1][mStr2.length() + 1];
// 计算最长公共序列的长度以及记录路径
public void LCS(String s1, String s2) {
for (int i = 0; i < s1.length(); i++) {
mLength[i][0] = 0;
}
for (int j = 0; j < s2.length(); j++) {
mLength[0][j] = 0;
}
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
// 字符相等,表中数据加1,用“↖”表示从对角线返回
if (s1.charAt(i) == s2.charAt(j)) {
mLength[i + 1][j + 1] = mLength[i][j] + 1;
mPath[i + 1][j + 1] = "↖";
}
// 当前两个字符不相等,表中数据继承上方的数据,用“↑”表示向上返回
else if (mLength[i][j + 1] >= mLength[i + 1][j]) {
mLength[i + 1][j + 1] = mLength[i][j + 1];
mPath[i + 1][j + 1] = "↑";
}
// 表中数据继承左方的数据,用“←”表示向左返回
else {
mLength[i + 1][j + 1] = mLength[i + 1][j];
mPath[i + 1][j + 1] = "←";
}
}
}
}// end LCS
// 输出最长公共序列
public void print_LCS(String[][] path, String str1, int str1_length, int str2_length) {
// 其中一个字符串为空,返回
if (str1_length == -1 || str2_length == -1) {
return;
}
// 对角线返回
if (path[str1_length + 1][str2_length + 1] == "↖") {
print_LCS(path, str1, str1_length - 1, str2_length - 1);
System.out.print(str1.charAt(str1_length));
}
// 向上返回
else if (path[str1_length + 1][str2_length + 1] == "↑") {
print_LCS(path, str1, str1_length - 1, str2_length);
}
// 向左返回
else
print_LCS(path, str1, str1_length, str2_length - 1);
}// end print_LCS
public static void main(String[] args) {
LCSProblem lcs = new LCSProblem();
lcs.LCS(lcs.mStr1, lcs.mStr2);
lcs.print_LCS(lcs.mPath, lcs.mStr1, lcs.mStr1.length() - 1, lcs.mStr2.length() - 1);
System.out.print(" length:"+lcs.mLength[lcs.mStr1.length()][lcs.mStr2.length()]);
}
分享到:
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
最长公共子序列问题 最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含...
由此函数,把序列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),...
C++求最长公共子序列!实用 花费了好长时间!!
算法导论实验 最长公共子序列程序源码 实验报告
最长公共子序列的算法实现,采用递归方法。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
实现了求最长公共子序列的算法,内容简单易懂,代码也很短