最長公共子序列

最長公共子序列（LCS）是一個在一個序列集合中（通常為兩個序列）用來查找所有序列中最長子序列的問題。這與查找最長公共子串的問題不同的地方是：子序列不需要在原序列中占用連續的位置。最長公共子序列問題是一個經典的計算機科學問題，也是數據比較（英語：data comparison）程序，比如Diff工具，和生物信息學應用的基礎。它也被廣泛地應用在版本控制，比如Git用來調和文件之間的改變。

定義

一個數列 $S$ ，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則 $S$ 稱為已知序列的最長公共子序列。

複雜度

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

兩個序列的解法

最長公共子序列問題存在最優子結構：這個問題可以分解成更小，更簡單的「子問題」，這個子問題可以分成更多的子問題，因此整個問題就變得簡單了。最長公共子序列問題的子問題的解是可以重複使用的，也就是說，更高級別的子問題通常會重用低級子問題的解。擁有這個兩個屬性的問題可以使用動態規劃算法來解決，這樣子問題的解就可以被儲存起來，而不用重複計算。這個過程需要在一個表中儲存同一級別的子問題的解，因此這個解可以被更高級的子問題使用。

動態規劃的一個計算最長公共子序列的方法如下，以兩個序列 $X$ 、 $Y$ 為例子：

設有二維數組 $f[i][j]$ 表示 $X$ 的 $i$ 位和 $Y$ 的 $j$ 位之前的最長公共子序列的長度，則有：

f[1][1]=same(1,1)

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

其中， $same(a,b)$ 當 $X$ 的第 $a$ 位與 $Y$ 的第 $b$ 位完全相同時為「1」，否則為「0」。

此時， $f[i][j]$ 中最大的數便是 $X$ 和 $Y$ 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。

該算法的空間、時間複雜度均為 $O(n^{2})$ ，經過優化後，空間複雜度可為 $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]

參見

引用

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

外部連結

（英文） longest common subsequence （頁面存檔備份，存於網際網路檔案館）
（英文） Longest Common Subsequences （頁面存檔備份，存於網際網路檔案館）

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

[1]