算法系列之六：最长公共子序列（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& str2, std::string& lcs)

181{

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

183 return;

184

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

186 {

187 lcs += str1[0];

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

189 }

190 else

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);

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

199 lcs = strLongest;

200 }

201}

二、 两重循环方法

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

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

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

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

154{

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

156

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

158 {

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

160 {

161 std::string lstr = LeftAllignLongestSubString(str1.substr(i), str2.substr(j));

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

163 lcs = lstr;

164 }

165 }

166}

其中LeftAllignLongestSubString()函数的作用就是从某个对齐位置开始匹配最长公共子串，其实现过程就是逐个比较字符，并记录最长子串的位置信息。

三、 改进后的算法

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

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

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

105void RelationLCS(const std::string& str1, const std::string& str2, std::string& lcs)

106{

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

108 int length = 0;

109

110 InitializeRelation(str1, str2, d);

111 int 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{

65 int k,longestStart,longs;

66 int longestI = 0;

67 int longi = 0;

68

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

70 {

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

72 if(longi > longestI)

73 {

74 longestI = longi;

75 longestStart = longs;

76 }

77 }

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

79 {

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

81 if(longi > longestI)

82 {

83 longestI = longi;

84 longestStart = longs;

85 }

86 }

87

88 *length = longestI;

89 return longestStart;

90}

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

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

参考资料：

【1】http://en.wikipedia.org/wiki/Longest_common_subsequence_problem