LCS(最长公共子序列)及其O(n)空间优化，O(nlogn)时间复杂度优化

LCS(最长公共子序列)及其O(n)空间优化，O(nlogn)时间复杂度优化

n^2 的版本

int LCS_n_2(vector<char> &a,vector<char> &b)
{
    vector<vector<int>> dp(a.size(),vector<int>(b.size(), 0));for(int i = 0;i<a.size();++i) if (a[i] == b[0]) dp[i][0] = 1;for(int j = 0;j<b.size();++j) if (a[0] == b[j]) dp[0][j] = 1;for(int i = 1;i<a.size();++i)for(int j = 1;j<b.size();++j){
    if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}return dp[a.size()-1][b.size()-1];
}

此时注意到其实每次算dp只需要三个数，dp[i][j],dp[i-1][j],dp[i][j-1]，那么只要保存一行的dp，后续直接更新即可，于是空间复杂度可以优化为 $O(N)$

template<typename vec>
int LCS_n(vec &a,vec &b)
{
    vector<int> dp(b.size()+1,0);int last = 0;for(int i = 1;i<=a.size();++i){
    last = 0;for(int j = 1;j<=b.size();++j){
    if(a[i-1] == b[j-1]){
    int tmp = last;last = dp[j-1] + 1;if(j-1>0)dp[j-1] = tmp;}else{
    int tmp = last;last = max(last,dp[j]);if(j-1>0)dp[j-1] = tmp;}//show(dp);}dp[b.size()] = last;}return last;
}

那么其实还有一种可以把时间复杂度优化到$O(nlogn)$的方法。

总的来说，就是把LCS转化成LIS，然后用LIS的NlogN算法来求解。
实现如下：（引用）
假设有两个序列 s1[ 1~6 ] = { a, b, c , a, d, c }, s2[ 1~7 ] = { c, a, b, e, d, a, b }。
记录s1中每个元素在s2中出现的位置, 再将位置按降序排列, 则上面的例子可表示为：loc( a）= { 6, 2 }, loc( b ) = { 7, 3 }, loc( c ) = { 1 }, loc( d ) = { 5 }。
将s1中每个元素的位置按s1中元素的顺序排列成一个序列s3 = { 6, 2, 7, 3, 1, 6, 2, 5, 1 }。
在对s3求LIS得到的值即为求LCS的答案。

可以参考下列实现

int LCS_n_logn(vector<char> &a,vector<char> &b)
{
    unordered_map<char,vector<int> >dp;for(int i = 0;i<a.size();++i){
    if(dp.count(a[i]) == 0)dp[a[i]].push_back(-1);}for(int i = 0;i<b.size();++i){
    if(dp.count(b[i]) == 1)dp[b[i]].push_back(i+1);}vector<int> dp2;for(int i = 0;i<a.size();++i){
    if(dp[a[i]].size() > 1){
    for(int j = dp[a[i]].size() - 1; j > 0; --j)dp2.push_back(dp[a[i]][j]);}}return LIS(dp2);
}