最长公共子序列

提示：此条目的主题不是最长公共子串。

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较（英语：data comparison）程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。

定義

一个数列${\displaystyle S}$，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则${\displaystyle S}$称为已知序列的最长公共子序列。

複雜度

對於一般性的LCS問題（即任意數量的序列）是屬於NP-hard。但當序列的數量確定時，問題可以使用动态规划（Dynamic Programming）在多項式時間内解決。[1]

两个序列的解法

最长公共子序列问题存在最优子结构：这个问题可以分解成更小，更简单的“子问题”，这个子问题可以分成更多的子问题，因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的，也就是说，更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决，这样子问题的解就可以被储存起来，而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解，因此这个解可以被更高级的子问题使用。

动态规划的一个计算最长公共子序列的方法如下，以两个序列${\displaystyle X}$、${\displaystyle Y}$为例子：

设有二维数组${\displaystyle f[i][j]}$表示${\displaystyle X}$的${\displaystyle i}$位和${\displaystyle Y}$的${\displaystyle j}$位之前的最长公共子序列的长度，则有：

${\displaystyle f[1][1]=same(1,1)}$

${\displaystyle f[i][j]=max\{f[i-1][j-1]+same(i,j),f[i-1][j],f[i][j-1]\}}$

其中，${\displaystyle same(a,b)}$当${\displaystyle X}$的第${\displaystyle a}$位与${\displaystyle Y}$的第${\displaystyle b}$位完全相同时为“1”，否则为“0”。

此时，${\displaystyle f[i][j]}$中最大的数便是${\displaystyle X}$和${\displaystyle Y}$的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。

该算法的空间、时间复杂度均为${\displaystyle O(n^{2})}$，经过优化后，空间复杂度可为${\displaystyle O(n)}$。

计算LCS的长度

下面算法计算了所有子问题的最长公共子序列长度C[i,j]。

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

参见

• 莱文斯坦距离
• Floyd-Warshall算法
• Viterbi算法

引用

1. 屈, 婉玲. 算法设计与分析. 北京清华大学学研大厦A座: 清华大学出版社. 2011: 67. ISBN 978-7-302-24756-2. 

外部連結

• （英文） longest common subsequence （页面存档备份，存于互联网档案馆）
• （英文） Longest Common Subsequences （页面存档备份，存于互联网档案馆）