最长公共子序列

Feb 27, 2017 | 算法总结 | 阅读

问题描述

求两个字符串的最长公共子序列（Longest Common Subsequence ( LCS )）。

算法

分别记两个字符串为$S_1$和$S_2$，它们的最长公共子序列为$LCS(S_1,S_2)$。

朴素的做法

枚举出$S_1$所有的子序列和$S_2$比较，时间复杂度：$O(2^{|S_1|}|S_2|)$。

动态规划的做法

记$S_1$和$S_2$最后的字符分别是$S_1$和$S_2$，即：$$S_1=S_1’+e_1$$ $$S_2=S_2’+e_2$$
有四种情况：

$LCS$包含$e_1$ 不含$e_2$
$LCS$包含$e_2$ 不含$e_1$
$LCS$不含$e_1$，$e_2$
$LCS$包含$e_1$，$e_2$

对于第一种情况，$e_2$没有用处，$LCS(S_1,S_2)=LCS(S_1,S_2’)$。
对于第二种同理，$LCS(S_1,S_2)=LCS(S_1’,S_2)$
对于第三种同理，$LCS(S_1,S_2)=LCS(S_1’,S_2’)$
对于第四种同理，$LCS(S_1,S_2)=LCS(S_1’,S_2’)+e_1$
如果使用非递归的做法，要保存前缀串的$LCS$，可以用动态规划实现。定义$dp[i][j]$表示$S_1$的前$i$个字符和$S_2$的前$j$个字符的$LCS$的长度，状态转移方程：
$$dp[i][j]=max \left \{ dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1 (S_{1_{i}}=S_{2_{j}}) \right \}$$
如果要求得到一个最长公共子序列，用一个二维数组记录状态是从哪一个转移来的即可，递归打印。
时间复杂度：$O(|S_1||S_2|)$

优化

如果用滚动数组优化，空间复杂度降至：$O(2|S|)$

基于位运算的算法

压位最长公共子序列（论文，代码）

Hunt-Szymanski Algorithm

转换为二维LIS问题

从两序列中找出对应的相同元素，以位置数对表示。这些位置数对可以排出的最长严格递增序列，即是两序列的$LCS $。
首先將所有数对排序，规则是第一个维度由小到大排序，当第一个维度相等时，第二个維度由大到小排序。排序之后，第二个维度的$1D$ $LIS$，就对应到原数对们的$2D$ $LIS$。

记数对的总数目为$K$，时间复杂度：$O(Klog |S|)$
如果出现类似于：$S_1=aaaa$，$S_2=aaaaaa$，时间复杂度退化成：$O(|S|^2log |S|)$

代码

//DP
for (int i=1; i<=n; ++i) {
    now ^= 1;
    for (int j=1; j<=m; ++j) {
        dp[now][j] = max(dp[now^1][j], dp[now][j-1]);
        if (s[i] == t[j]) dp[now][j] = max(dp[now][j], dp[now^1][j-1]+1);
    }
}  //lcs = dp[now][m];

//2D LIS
int LCS(char *s, char &t) {
	int n = strlen(s+1), m = strlen(t+1);
    vector<int> pos[128];
    for (int i=1; i<=m; ++i) {
        pos[t[i]].push_back(i);
    }
    vector<int> lcs;
    for (int i=1; i<=n; ++i) {
        for (int j=(int)pos[s[i]].size()-1; j>=0; --j) {
            int p = pos[s[i]][j];
            if (lcs.empty()) lcs.push_back(p);
            else if (p > lcs.back()) lcs.push_back(p);
            else *lower_bound(lcs.begin(), lcs.end(), p) = p;
        }
    }
    return lcs.size();
}

习题

UVA 111（简单题）
POJ 2250（打印LCS）
POJ 1159（滚动数组优化）
UVA 10635 UVA 10949（2D LIS）
玲珑学院OJ 1097 （2D LIS）

拓展

最长公共上升子序列
最长回文子序列
最长公共子串

参考资料

演算法笔记 - Longest Common Subsequence

动态规划 LCS