当前位置：搜档网 › 算法系列之六：最长公共子序列(LCS)问题(连续子序列)的三种解法

算法系列之六：最长公共子序列(LCS)问题(连续子序列)的三种解法

算法系列之六：最长公共子序列（LCS）问题（连续子序列）的三种解法

最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列必须连续。上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求子序列必须是连续的情况下如何用算法解决最长公共子序列问题。

仍以上一章的两个字符串“abcdea”和“aebcda”为例，如果子序列不要求连续，其最长公共子序列为“abcda”，如果子序列要求是连续，则其最长公共子序列应为“bcd”。在这种情况下，有可能两个字符串出现多个长度相同的公共子串，比如“askdfiryetd”和“trkdffirey”两个字符串就存在两个长度为3的公共子串，分别是“kdf”和“fir”，因此问题的性质发生了变化，需要找出两个字符串所有可能存在公共子串的情况，然后取最长的一个，如果有多个最长的公共子串，只取其中一个即可。

字符串“abcdea”和“aebcda”如果都以最左端的a字符对齐，则能够匹配的最长公共子串就是“a”。但是如果用第二个字符串的e字符对齐第一个字符串的a 字符，则能够匹配的最长公共子串就是“bcd”。可见，从两个字符串的不同位置开始对齐匹配，可以得到不同的结果，因此，本文采用的算法就是穷举两个字符串所有可能的对齐方式，对每种对齐方式进行字符的逐个匹配，找出最长的匹配子串。

一、递归方法

首先看看递归方法。递归的方法比较简单，就是比较两个字符串的首字符是否相等，如果相等则将其添加到已知的公共子串结尾，然后对两个字符串去掉首字符后剩下的子串继续递归匹配。如果两个字符串的首字符不相等，则用三种对齐策略分别计算可能的最长公共子串，然后取最长的一个与当前已知的最长公共子串比较，如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串。第一种策略是将第一个字符串的首字符删除，将剩下的子串与第二个字符串继续匹配；第二种策略是将第二个字符串的首字符删除，将剩下的子串与第一个字符串继续匹配；第三种策略是将两个字符串的首字符都

删除，然后继续匹配两个字符串剩下的子串。删除首字符相当于字符对齐移位，整个算法实现如下：

180void RecursionLCS(const std::string& str1,const std::string& st r2,std::string& lcs)

181{

182if(str1.length()==0|| str2.length()==0)

183return;

184

185if(str1[0]== str2[0])

186{

187 lcs += str1[0];

188 RecursionLCS(str1.substr(1), str2.substr(1), lcs);

189}

190else

191{

192 std::string strTmp1,strTmp2,strTmp3;

193

194 RecursionLCS(str1.substr(1), str2, strTmp1);

195 RecursionLCS(str1, str2.substr(1), strTmp2);

196 RecursionLCS(str1.substr(1), str2.substr(1), strTmp3); 197 std::string

strLongest = GetLongestString(strTmp1, strTmp2, strTmp3);

198if(lcs.length()< strLongest.length())

199 lcs = strLongest;

200}

201}

二、两重循环方法

使用两重循环进行字符串的对齐匹配过程如下图所示：

图（1）两重循环字符串对齐匹配示意图

第一重循环确定第一个字符串的对齐位置，第二重循环确定第二个字符串的对齐位置，每次循环确定一组两个字符串的对齐位置，并从此对齐位置开始匹配两个字符串的最长子串，如果匹配到的最长子串比已知的（由前面的匹配过程找到的）最长子串长，则更新已知最长子串的内容。两重循环的实现算法如下：

153void LoopLCS(const std::string& str1,const std::string& str2, s td::string&lcs)

154{

155 std::string::size_type i,j;

156

157for(i =0; i < str1.length(); i++)

158{

159for(j =0; j < str2.length(); j++)

160{

161 std::string

lstr = LeftAllignLongestSubString(str1.substr(i),str2.substr(j));

162if(lstr.length()> lcs.length())

163 lcs = lstr;

164}

165}

166}

其中LeftAllignLongestSubString()函数的作用就是从某个对齐位置开始匹配最

长公共子串，其实现过程就是逐个比较字符，并记录最长子串的位置信息。三、改进后的算法

使用两重循环的算法原理简单，LoopLCS()函数的实现也简单，时间复杂度为O(n2)（或O(mn)），比前一个递归算法的时间复杂度O(3n)要好很多。但是如果仔细观察图（1）所示的匹配示意图，就会发现这个算法在m x n次循环的过程中对同一位置的字符进行多次重复的比较。比如i=1，j=0的时候，从对齐位置开始第二次比较会比较第一个字符串的第三个字符“c”与第二个字符串的第二个字符“e”，而在i=1，j=0的时候，这个比较又进行了一次。全部比较的次数可以近似计算为mn(n-1)/2（其中m和n分别为两个字符串的长度），也就是说比较次数是O(n3)数量级的。而理论上两个字符串的不同位置都进行一次比较只需要mn次比较即可，也就是说比较次数的理论值应该是O(n2)数量级。

考虑对上述算法优化，可以将两个字符串每个位置上的字符的比较结果保存到一张二维表中，这张表中的[i,j]位置就表示第一个字符串的第i个字符与第二个字符串的第j个字符的比较结果，1表示字符相同，0表示字符不相同。在匹配最长子串的过程中，不必多次重复判断两个字符是否相等，只需从表中的[i,j]位置直接得到结果即可。

改进后的算法分成两个步骤：首先逐个比较两个字符串，建立关系二维表，然后用适当的方法搜索关系二维表，得到最长公共子串。第一个步骤比较简单，算法的改进主要集中在从关系二维表中得到最长公共子串的方法上。根据比较的原则，公共子串都是沿着二维表对角线方向出现的，对角线上连续出现1就表示这个位置是某次比较的公共子串。有上面的分析可知，只需要查找关系二维表中对角线上连续出现的1的个数，找出最长的一串1出现的位置，就可以得到两个字符串的最长公共子串。改进后的算法实现如下：

105void RelationLCS(const std::string& str1,const std::string& str

2, std::string&lcs)

106{

107int d[MAX_STRING_LEN][MAX_STRING_LEN]={0};

108int length =0;

109

110 InitializeRelation(str1, str2, d);

111int pos = GetLongestSubStringPosition(d, str1.length(), str2 .length(),&length);

112 lcs = str1.substr(pos, length);

113}

InitializeRelation()函数就是初始化二维关系表，根据字符比较的结果将d[i,j]相应的位置置0或1，本文不再列出。算法改进的关键在GetLongestSubStringPosition()函数中，这个函数负责沿对角线搜索最长公共子串，并返回位置和长度信息。仍然以字符串“abcdea”和“aebcda”为例，InitializeRelation()函数计算得到的关系表如图（2）所示：

图（2）示例字符串的位置关系示意图

从图（2）中可以看到，最长子串出现在红线标注的对角线上，起始位置在第一个字符串（纵向）中的位置是2，在第二个字符串（横向）中的位置是3，长度是3。搜索对角线从两个方向开始，一个是沿着纵向搜索左下角方向上的半个关系矩阵，另一个是沿着横向搜索右上角方向上的半个关系矩阵。对每个对角线分别查找连续的1出现的次数和位置，并比较得到连续1最多的位置。GetLongestSubStringPosition()函数的代码如下：

63int GetLongestSubStringPosition(int d[MAX_STRING_LEN][MAX_STRING_ LEN],int m,int n,int*length)

64{

65int k,longestStart,longs;

66int longestI =0;

67int longi =0;

69for(k =0; k < n; k++)

70{

71 longi = GetLongestPosition(d, m, n,0, k,&longs);

72if(longi > longestI)

73{

74 longestI = longi;

75 longestStart = longs;

76}

77}

78for(k =1; k < m; k++)

79{

80 longi = GetLongestPosition(d, m, n, k,0,&longs);

81if(longi > longestI)

82{

83 longestI = longi;

84 longestStart = longs;

85}

86}

88*length = longestI;

89return longestStart;

90}

GetLongestPosition()函数就是沿着对角线方向搜索1出现的位置和连续长度，算法简单，本文不再列出。

至此，本文介绍了三种要求子串连续的情况下的求解最长公共子串的方法，都是简单易懂的方法，没有使用复杂的数学原理。第一种递归方法的时间复杂度是O(3n)，这个时间复杂度的算法在问题规模比较大的情况下基本不具备可用性, 第三种方法是相对最好的方法，但是仍有改进的余地，比如使用位域数组，可以减少存储空间的使用，同时结合巧妙的位运算技巧，可以极大地提高GetLongestPosition()函数的效率。

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

算法作业： LCS 问题作业要求：设计一个算法求出两个序列的所有LCS ，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度，定义C[i][j]如下： { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或，且为了构造出LCS ，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS ，定义数组b 如下：设1-对角线方向;2-向上;3-向左;4-向上或向左若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j][i][j-1], 则b[i][j] = 3, 若C[i-1][j]=[i][j-1], 则b[i][j] = 4, 根据以上辅助数组C 和b 的定义，算法首先需要求出这两个数组， C[m][n]中记录的最长公共子序列的长度，b 中记录了查找子序列元素的搜索方向。利用C 和b 的信息，Find_All_LCS 可以采用回溯法求出所有的LCS 。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS 得到的LCS 中的元素，每次递归调用一次Find_All_LCS ，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS ，按序输出；若不等于，此时根据数组b 中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS ，保证沿着这两个方向上LCS 元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素X[i]为LCS 中的元素，存放至辅助数组中去，同时将当前已经求得的LCS 长度增1，当递归调用Find_All_LCS 从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS ，这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。 2、时间复杂度分析由上述对Find_All_LCS 算法的分析可知，求出所有的LCS 实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此，除求解辅助数组C 和b 所用的O(mn+m+n)的执行时间外，Find_All_LCS 的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下，即m=n 并且b 中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n). 相反，当X 和Y 序列不存在公共子序列时为算法的最坏情况，此时C 中所有值都等于0，数组b 中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS ，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜索矩阵如下图所示：

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

程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言程序员编程艺术系列重新开始创作了（前十章，请参考程序员编程艺术第一~十章集锦与总结）。回顾之前的前十章，有些代码是值得商榷的，因当时的代码只顾阐述算法的原理或思想，所以，很多的与代码规范相关的问题都未能做到完美。日后，会着力修善之。搜遍网上，讲解这个LCS问题的文章不计其数，但大多给读者一种并不友好的感觉，稍感晦涩，且代码也不够清晰。本文力图避免此些情况。力保通俗，阐述详尽。同时，经典算法研究系列的第三章（三、dynamic programming）写的极其糟糕，所以，也算是对那文的一种弥补。有任何问题，欢迎不吝赐教。第一节、问题描述什么是最长公共子序列呢?好比一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。举个例子，如：有两条随机序列，如1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。第二节、LCS问题的解决思路 ?穷举法解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m * 2^n）。 ?动态规划算法事实上，最长公共子序列问题也有最优子结构性质。记: Xi=﹤x1，?，xi﹥即X序列的前i个字符(1≤i≤m)（前缀） Yj=﹤y1，?，yj﹥即Y序列的前j个字符(1≤j≤n)（前缀）假定Z=﹤z1，?，zk﹥∈LCS(X , Y)。