vlambda博客
学习文章列表

最长公共子序列(LCS)问题

本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法。编程学习最好使用计算机,请登陆 www.3dian14.org (免费注册,免费学习)。


本课我们来讨论最长的公共子序列(Longest Common Subsequence,LCS)问题,它也是动态编程的经典问题。


先看一下LCS问题的描述。


给定两个序列,找出两个序列中都存在的最长子序列的长度。子序列是指以相同的相对顺序出现,但不一定是连续的序列。


例如, “abc”, “abg”, “afg”, “bdf”, “aeg”, “acefg”等等都是存在于序列 “abcdefg”中的子序列。


而“ag”, “afc”, “afg”, “fce”, “acefg”, “cefag”等等都是序列“agfcefag”的子序列。


现在需要找出存在于上述两个序列中的公共子序列,并且它的长度是最长的。这里的“acefg”就是最长的LCS,长度为5。


再看两个例子:

1)对于输入序列“ABCDGH”和“AEDFHR”,  “ADH”是最长的公共子序列,长度为3。


2)对于输入序列“AGGTAB”和“GXTXAYB”,  “GTAB”是最长的公共子序列,长度为4。


这是一个经典的计算机科学问题,它也是diff程序(一种可以比较和输出两个文件的内容差异的程序)的基础,并已在生物信息学中得到应用。




暴力破解法


这个问题的朴素解决方案是暴力破解法:生成两个给定序列的所有子序列,逐个进行比对,找到匹配的公共子序列,并且从中取最长的匹配子序列。


为了找出暴力破解方法的复杂性,我们首先需要知道长度为n的字符串的可能不同子序列的数量,即找到长度为1,2,.. n-1的子序列的数量。


从排列组合理论中可知,

具有1个元素的组合数为最长公共子序列(LCS)问题

具有2个元素的组合数为最长公共子序列(LCS)问题


依此类推。我们知道

最长公共子序列(LCS)问题

由于我们不考虑长度为0的子序列,因此长度为n的字符串具有最长公共子序列(LCS)问题个不同的可能子序列。这意味着暴力破解方案的时间复杂度为最长公共子序列(LCS)问题。这里注意,检查一个子序列是否是两个字符串的公共子序列需要最长公共子序列(LCS)问题时间。


因此暴力破解方案在时间复杂度方面是指数级的。用动态编程可以改善时间复杂度。


最长公共子序列(LCS)问题

动态编程法-最佳子结构


我们来看看如何采用动态编程解决上述问题。


令输入序列分别保存在为长度为mn的两个数组X[0..m-1]Y[0..n-1]


并令L(X[0..m-1], Y[0..n-1]) 为两个序列XY的LCS的长度。


以下是L(X[0..m-1], Y[0..n-1]) 的递归定义:


1)如果两个序列的最后一个字符都匹配(或X[m-1] == Y[n-1]),则


L(X[0..m-1], Y[0..n-1]) = 1+L(X[0..m-2], Y[0..n-2])


2)如果两个序列的最后一个字符都不匹配(或X [m-1]!= Y [n-1]),则


L(X[0..m-1], Y[0..n-1]) = MAX(L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]))


例子:


1)  考虑输入字符串“AGGTAB”和“GXTXAYB”。两个字符串的最后一个字符“B”相匹配。因此,LCS的长度可以写成:

       

L(“AGGTAB”,“GXTXAYB”) = 1 + L (“AGGTA”, “GXTXAY”)


这里的1是匹配的字符“B”的长度,L (“AGGTA”, “GXTXAY”)表示去除“B”后剩下的两个新字符串的LCS。


2)考虑输入字符串“ABCDGH”和“AEDFHR”。字符串的最后一个字符不匹配。因此,LCS的长度可以写成:


L(“ABCDGH”, “AEDFHR”) = MAX(L(“ABCDG”, “AEDFHR”),L(“ABCDGH”, “AEDFH”))


这里L(“ABCDG”, “AEDFHR”)是字符串“ABCDG”取出最后一个字符“H”后,所得到的新字符串“ABCDG” 与原来的另一个字符串“AEDFHR”,再一起求出的LCS。


L(“ABCDGH”, “AEDFH”)是字符串“AEDFHR”取出最后一个字符“R”后,所得到的新字符串“AEDFH” 与原来的另一个字符“ABCDGH”,再一起求出的LCS。


上述两个LCS值中较大的值就是原有两个字符串的LCS。


下面的图是求L(“AGGTAB”,“GXTXAYB”)的过程示意图(注意是示意图)。


最长公共子序列(LCS)问题

下是LCS问题的简单递归实现, 它遵循上述递归结构。


/* C++程序:上述问题的简单递归实现 */

#include <bits/stdc++.h> 

using namespace std; 


int max(int a, int b); 


/* 返回 X[0..m-1], Y[0..n-1]中的LCS长度 */

int lcs( char *X, char *Y, int m, int n ) 

if (m == 0 || n == 0) 

return 0; 

if (X[m-1] == Y[n-1]) 

return 1 + lcs(X, Y, m-1, n-1); 

else

return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 


/* 取出两数字的较大者*/

int max(int a, int b) 

return (a > b)? a : b; 


/* 主程序 */

int main() 

char X[] = "AGGTAB"; 

char Y[] = "GXTXAYB"; 


int m = strlen(X); 

int n = strlen(Y); 


cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ; 


return 0; 


试输入上述程序并运行。


最长公共子序列(LCS)问题

动态编程法-重叠子问题


上述朴素递归方法的时间复杂度在最坏情况下为最长公共子序列(LCS)问题。最坏情况发生在XY的所有字符不匹配(即LCS的长度为0)时。


考虑到以上实现,下面是输入字符串“AXYT”和“AYZX”的部分递归树

                  

在上面的部分递归树中,lcs(“AXY”,“AYZ”)被求解了两次。如果我们绘制完整的递归树,则可以看到有很多子问题可以一次又一次地被重复计算。因此,此问题具有“重叠子结构”属性,可以通过使用“记忆方式”或“列表方式”来避免相同子问题的重新计算。以下是LCS问题的列表方式的实现。


/*  解决LCS的动态编程法 C++代码例子 */

#include<bits/stdc++.h> 

using namespace std; 


int max(int a, int b); 


/* 返回 X[0..m-1], Y[0..n-1]中的LCS长度 */

int lcs( char *X, char *Y, int m, int n ) 

int L[m + 1][n + 1]; 

int i, j; 


/* Following steps build L[m+1][n+1] in 

bottom up fashion. Note that L[i][j] 

contains length of LCS of X[0..i-1] 

and Y[0..j-1] */

        /*从下而上构造 L[m+1][n+1]*/

        /*L[i][j] 包含X[0..i-1]和Y[0..j-1]的LCS长度*/

for (i = 0; i <= m; i++) 

for (j = 0; j <= n; j++) 

if (i == 0 || j == 0) 

L[i][j] = 0; 


else if (X[i - 1] == Y[j - 1]) 

L[i][j] = L[i - 1][j - 1] + 1; 


else

L[i][j] = max(L[i - 1][j], L[i][j - 1]); 


        /*L[m][n] 包含X[0..n-1]和Y[0..m-1]的LCS长度*/

return L[m][n]; 


/* 取出两数字的较大者*/

int max(int a, int b) 

return (a > b)? a : b; 


// 主程序

int main() 

char X[] = "AGGTAB"; 

char Y[] = "GXTXAYB"; 


int m = strlen(X); 

int n = strlen(Y); 


cout << "Length of LCS is "

<< lcs( X, Y, m, n ); 


return 0; 


试输入上述程序并运行。


上述实现的时间复杂度为。比朴素递归算法实现的最坏情况下的时间复杂度好得多。