最长公共子序列

最长公共子序列問題是尋找两个或多个已知数列最長的子序列。

定義

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

複雜度

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

解法

动态规划的一个计算最长公共子序列的方法如下，以两个序列 $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)$，时间复杂度为$O(n\log n)$。

代码

int
longest_common_subsequence_length
(
    int * begin,
    int * end
)
{
    int n = end - begin;
    int * temp = new int[n];
    int used = 0;
 
    for(int i = 0; i < n; ++ i)
    {
        int * p = std::lower_bound(temp + 0, temp + used, begin[i]);
 
        * p = begin[i];
 
        // insert at `end'
        if(p == temp + used)
        {
            ++ used;
        }
    }
 
    delete [] temp;
 
    return used;
}

外部連結

• （英文） longest common subsequence
• （英文） Longest Common Subsequences