/**
* 动态规划之最长公共子序列问题:给定一个子序列 X = <x1,x2,...xm>,另一个子序列Z = <z1,z2,...zk>是X的子序列,如果存在X的一个严格递增下标序列
* <i1,i2,...ik>,使得对于所有j = 1,2,...k,有xij = zj。如Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>子序列,对应下标i = <2,3,5,7>
* LCS问题:给定序列X=<x1,x2,...xn>和Y=<y1,y2...ym>,找出X和Y的最长公共子序列
* 设Z<z1,z2,...zk>是X和Y的任一个最长公共子序列,那么:
* 1) 若xn = ym,则zk = xn = ym 而且<z1,z2,...zk-1>是Xn-1和Ym-1的最长公共子序列
* 2) 若xn != ym 则zk!=xn 蕴含Z是Xn-1和Y的一个LCS
* 3) 若ym != xn 则zk!= ym蕴含Z是x和Ym-1的一个LCS
*
* 基于以上结论,可以得出一个递归解:
* 定义c[i][j]是序列Xi和Yj的LCS的长度则:
* --> 0 if i = 0 或者 j = 0
* c[i][j] = --> c[i-1][j-1] + 1 如果i>0,j>0,xi=yj
* --> max{c[i-1][j],c[i][j-1]} 如果i>0,j>0,xi != yj
* @author song
*
*/
/**
* 计算x和y的公共子序列长度表
* @param x
* @param y
* @return
*/
public static int[][] calculateCommonSubsequenceNum(char[] x, char[] y){
int n = x.length;
int m = y.length;
//记录各个LCS长度的二维表
int[][] c = new int[n+1][m+1];
//初始化:c[i][j] = 0 当i=0 or j=0
for(int i = 0; i <= m; ++i)
c[0][i] = 0;
for(int j = 0; j <= n; ++j)
c[j][0] = 0;
//注意c[1][1]记录的是 x[0]和y[0]的公共子序列长度,因为x和y的第一个元素不是x[1]和y[1],而是x[0]和y[0]
for( int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if( x[i-1] == y[j-1] )
c[i][j] = c[i-1][j-1] + 1;
else{
c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
}
}
}
return c;
}
/**
* 找出一个最长公共子序列
* 找出LCS依赖于 {@link #calculateCommonSubsequenceNum(char[], char[])}的LCS长度序列表
* 根据最初分析的三个结论
* 1)若Z是X和Y的LCS,若xn=ym,则zk = xn = ym即X和Y的最后一个字符肯定出现在LCS中
* 2)若xn != ym,则Z肯定是 Xn-1和Ym的LCS 以及 Xn和Ym-1的LCS中更长得那一个序列,也就是说当xn!=ym时,可以转化为找 Xn-1和Ym的LCS/ Xn和Ym-1的LCS
* 更进一步,若c[n-1][m] > c[n][m-1],找Xn-1和Ym的LCS即可,因为他更长,反之找Xn和Ym-1的LCS
* 因此,从后向前扫描x和y序列,碰到相同则将该字符放入LCS,
* 若不相同,则比较c[n-1][m] > c[n][m-1],根据他们的值比较xn-1和ym 或者 xn和ym-1
*
* @param x
* @param y
* @return
*/
public static List<Character> findLongestLCS(char[] x,char[] y){
List<Character> result = new LinkedList<Character>();
int c[][] = calculateCommonSubsequenceNum(x, y);
int n = x.length - 1;
int m = y.length - 1;
while( n >= 0 && m >= 0){
if(x[n] == y[m]){
result.add(0, x[n]);
n--;m--;
}else{
if(c[n][m+1] > c[n+1][m])
n--;
else
m--;
}
}
return result;
}
测试代码:
public static void main(String[] args) {
char[] x = "10010101".toCharArray();
char[] y = "010110110".toCharArray();
List<Character> r = findLongestLCS(x, y);
System.out.println("The longest LCS:" + r.toString());
}
result:The longest LCS:[0, 1, 0, 1, 0, 1]
分享到:
相关推荐
用动态规划算法来解决两个序列的最长公共子序列问题
最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
动态规划解决LCS
动态规划实现lcs
最长公共子序列(lcs)使用动态规划解决采用c++编写
算法导论中最长公共子序列的实现,采用动态规划方法
问题描述 东东有两个序列A和B。...这个题是基本的动态规划问题,LIS是最长上升子序列,LCS是最长公共子序列。 求解LIS就是设dp[i]为以当前元素结尾的最长上升序列,那么dp[i]=max(dp[j]∣j<i&&a
x,y两个序列,通过动态规划的方法来解决最长子序列的问题。
【ACM程序设计】动态规划 第二篇 LCS&LIS问题.doc
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS 1.实现基于优化子结构的递归求解算法 2.实现基于动态规划的求解算法 3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所...
LCS的一个实现,具体分析见我的博文《动态规划2》,大家一起学习,开发环境VS2008
1、了解什么是动态规划 2、斐波那契、爬楼梯、跳台阶等入门动态规划思想详细讲解 3、LCS、LIS等经典动态规划问题详解 4、打家劫舍系列问题分析 5、买卖股票最佳时间问题分析
LCS最长公共子序列c++的代码。动态规划思想
使用动态规划方法解决找零钱问题、最长公共字符串问题(LCS)、背包问题的源代码
动态规划求解并输出所有LCS
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
用LCS方法解决字符匹配问题,用到动态规划的思想。原创
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
使用c++语言编写的LCS问题的求解过程