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

        最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。其定义是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。

        关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列。另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。本文将介绍对子序列没有连续性要求的情况下如何用计算机解决最长公共子序列问题，对子序列有连续性要求的情况下如何用计算机解决最长公共子序列问题将在后续的文章中介绍。

一、    动态规划法（Dynamic Programming）

        最长公共子序列问题应该是属于多阶段决策问题中求最优解一类的问题，凡此类问题在编制计算机程序时应优先考虑动态规划法，如果不能用动态规划法，而且也找不到其它解决方法，还可以考虑穷举法。对于这个问题，只要能找到描述最长公共子序列的最优子结构和最优解的堆叠方式，并且保证最优子结构中的每一次最优决策都满足“无后效性”，就可以考虑用动态规划法。使用动态规划法的关键是对问题进行分解，按照一定的规律分解成子问题（分解后的子问题还可以再分解，这是个递归的过程），通过对子问题的定义找出最优子结构中最优决策序列（对于子问题就是最有决策序列的子序列）以及最优决策序列子序列的递推关系（当然还包括递推关系的边界值）。

        如果一个给定序列的子序列是在该序列中删去若干元素后得到的序列，也就意味着子序列在原序列中的位置索引（下标）保持严格递增的顺序。例如,序列S = <B,C,D,B>是序列K = <A，B，C，B，D，A，B>的一个子序列（非连续），序列S的元素在在K中的位置索引I = [2,3,5,7]，I是一个严格递增序列。

1.1           最优子结构定义与边界值

        现在来分析一下本问题的最优子结构。首先定义问题，假设有字符串str1长度为m，字符串str2长度为n，可以把子问题描述为：求字符串str1<1..m>中从第1个到第i（i <= m）个字符组成的子串str1<1…i>和字符串str2<1..n>中从第1个到第j(j <= n)个字符组成的子串str2<1…j>的最长公共序列，子问题的最长公共序列可以描述为d[i,j] = { Z1,Z2, … Zk }，其中Z1-Zk为当前子问题已经匹配到的最长公共子序列的字符。子问题定义以后，还要找出子问题的最优序列d[i,j]的递推关系。分析d[i,j]的递推关系要从str1[i]和str2[j]的关系入手，如果str1[i]和str2[j]相同，则d[i,j]就是d[i-1,j-1]的最长公共序列＋1，Zk=str1[i]=str2[j]；如果str1[i]和str2[j]不相同，则d[i,j]就是d[i-1,j]的最长公共序列和d[i,j-1]的最长公共序列中较大的那一个。

        最后是确定d[i,j]的边界值，当字符串str1为空或字符串str2为空时，其最长公共子串应该是0，也就是说当i=0或j=0时，d[i,j]就是0。d[i,j]的完整递推关系如下：

1.1           反求最长公共子序列

         根据1.1得到的最优解子结构递推关系，依次计算i从到m，j从1到n的d[i,j]值，最后得到的d[m,n]就是最长公共子序列的长度。d[m,n]只是最长公共子序列的长度值，表示了两个字符串的相似程度，如果要获得最长公共子序列，就需要在计算出d[m,n]矩阵的值后分析每一步决策的结果，根据每一个最优决策逆向构造出最长公共子序列。为此需要在递推计算d[i,j]的过程中，需要同时记录下最优决策的过程，最优决策的过程用矩阵r表示，r[i,j]表示最长公共子序列的长度值d[i,j]的“递推来源”。根据前面整理的递推关系，如果r[i,j]的值是1，则表示d[i,j]的值由d[i-1,j-1] + 1递推得到；如果r[i,j]的值是2，则表示d[i,j]的值由d[i-1,j]递推得到；如果r[i,j]的值是3，则表示d[i,j]的值由d[i,j-1]递推得到。以字符串“abcdea”和“aebcda”为例，根据递推关系得到的d和r合并到一个矩阵中显示：

图（1）逆向构造最长公共子序列示意图

逆向构造最长公共子串的过程从r[m,n]开始，如果r[i,j]＝1，则表示两个字符串中的str1[i]和str2[j]相同，可以将str1[i]或str2[j]插入到当前构造的最长公共子序列中。如果r[i,j]≠1，则不改变当前构造的最长公共子序列，但是要根据r[i,j]的值是2还是3，调整r[i,j]倒推的下一个位置。以上述两个字符串构造出的d矩阵和r矩阵为例，逆向构造最长公共子序列的过程如下：r[6,6]=1表示当前公共子串lcs = <str1[6]>（str1[6]和<str2[6]>值一样），同时前一次最优决策来自于d[5,5]。r[5,5]=2表示前一次决策来自于d[4,5]，此时r[4,5]=1，表示当前公共子串lcs = < str1[4]，str1[6]>，同时前一次最优决策来自于d[3,4]。r[3,4]=1表示当前公共子串lcs = < str1[3]，str1[4]，str1[6]>，同时前一次最优决策来自于d[2,3]。r[2,3]=1表示当前公共子串lcs = < str1[2]，str1[3]，str1[4]，str1[6]>，同时前一次最优决策来自于d[1,2]。r[1,2]=3表示前一次决策来自于d[1,1]，此时r[1,1]=1，表示当前公共子串lcs = < str1[1]，str1[2]，str1[3]，str1[4]，str1[6]>。由于r[0,0]是边界，因此逆向构造过程结束，得到最长公共子串的最终结果是lcs = < str1[1]，str1[2]，str1[3]，str1[4]，str1[6]>，对应的字符串就是<abcda>。

1.1           动态规划算法实现

        在编写实现代码时，将每次决策的策略和最优值用一个数据结构描述：

 d是最优决策的值，r是决策方向。整个算法分成两部分，首先根据递推关系得到最优值（包括决策方向），这部分由InitializeDpLcs()函数完成，然后是逆向构造出最长公共序列，由GetLcs()函数实现。InitializeDpLcs()函数实现了本文1.1小节介绍的d[i,j]的递推计算算法以及r[i,j]的构造过程：

GetLcs()函数则是1.2小节描述的算法实现，巧妙的利用了递归算法实现了逆向构造最长公共子串，构造过程基于第一个字符串，lcs就是最终得到的最长公共字串：

一、    穷举的方法

         除了动态规划法，求最长公共子序列问题也可以使用穷举算法。穷举算法的实质就是使用各种匹配两个字符串的方法，对两个字符串求解最长公共子串，然后找出各种方法得到子串中最长的一个。穷举法匹配字符串有很多种方法，本文介绍一种模仿人类思维方式，用递归方式求解最长公共子串的算法。

2.1        算法分析

        人脑解决此类问题的方法就是逐个比较两个字符串的每个字符，比如str1[i]和str2[j]，如果str1[i]==str2[j]，则将str1[i]或str2[j]附加到str1[i]和str2[j]之前计算得到的最长公共子串后面，然后继续计算str1[i+1]开始的子串和和str2[j+1]开始的子串的最长公共子串。如果str1[i]!=str2[j]，则采用三种方法穷举，第一种方法是删除str1[i]，继续计算str1[i+1]开始的子串和str2[j]开始的子串的最长公共子串；第二种方法是删除str2[j]，继续计算str1[i]开始的子串和str2[j+1]开始的子串的最长公共子串；第三种方法是删除str1[j]和str2[j]，继续计算str1[i+1]开始的子串和str2[j+1]开始的子串的最长公共子串。使用三种方法计算完成后比较结果，取最长的子串附加到str1[i]和str2[j]之前计算得到的最长公共子串后面组成新的最长公共子串。以上继续计算都是递归过程，递归的终止条件是到达str1字符串结尾或str2字符串结尾。

2.2          算法实现

        RecursionLCS()函数就是对上述2.1分析的实现：

GetLongestString()是一个辅助函数，就是比较三个字符串，返回最长的一个字符串。

三、    总结

        本文给出的了两种求解最长公共子串的算法，毫无疑问，动态规划的算法要优于递归实现的穷举算法。使用递归实现的穷举算法代码简洁易懂，但是算法的时间复杂度在最坏的情况下是О(n3n)（最好情况下是О(n)），这样的算法只能作为理论存在，基本上不具备实用价值，写在这里只是为了与动态规划算法做对比。

参考书籍：

【1】算法艺术和信息学竞赛 刘汝佳、黄亮  清华大学出版社 2003年

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