LCS

阳光穿透心脏的1/2处 2023-03-01 10:47 74阅读 0赞

![博客图片][format_png]

## 问题描述 ##

从一个序列中删去某些元素可以得到一个子序列,对于序列`X`和`Y`,如果序列`Z`既是`X`的子序列又是`Y`的子序列,那么称`Z`是`X`和`Y`的公共子序列,长度最长的子序列称为最长公共子序列`LCS`.给定两个序列`X`和`Y`,计算的最长公共子序列的长度,输出一种可行的方案.

## 分析 ##

对于序列`X`和`Y`的公共子列来说,如果它们最后一个字母一样,那么它们的`LCS`一定是去掉最后一个字母的两个序列的`LCS`的长度加一;否则就是`X`去掉最后一个字母的序列和序列`Y`的`LCS`的长度与序列`Y`去掉最后一个字母的序列与序列`X`的`LCS`的长度的最大值,所以对于长度为`i`的序列`X`和长度为`j`的序列`Y`,它们的`LCS`的长度满足:

d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j − 1 \] , X \[ i \] = = Y \[ j \] m a x ( d p \[ i − 1 \] \[ j \] , d p \[ i \] \[ j − 1 \] ) X \[ i \]   ! = Y \[ j \] dp\[i\]\[j\]= \\begin\{cases\} dp\[i-1\]\[j-1\], \\qquad X\[i\]==Y\[j\]\\\\ max(dp\[i-1\]\[j\],dp\[i\]\[j-1\]) \\quad X\[i\]\\, !=Y\[j\] \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j−1\],X\[i\]==Y\[j\]max(dp\[i−1\]\[j\],dp\[i\]\[j−1\])X\[i\]!=Y\[j\]

然后可以用一个两重循环计算出结果,最后的`dp[i][j]`就是长度为`i`的序列`X`和长度为`j`的序列`Y`的`LCS`的长度,对应的代码如下:

void solve(const string & a, const string& b){
        
            memset(dp,0,sizeof(dp));
            for(int i = 1;i <= a.length(); ++i){
        
                for(int j = 1;j <= b.length(); ++j){
        
                    if(a[i-1] == b[j-1]){
        
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
        
                        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            printf("%lld\n", dp[a.length()][b.length()]);
        }

路径的打印需要从后向前看,判断`dp[i][j]==dp[i-1][j]`和`dp[i][j]==dp[i][j-1]`,相等表示此时的`LCS`和 X i − 1 , Y j X\_\{i-1\},Y\_j Xi−1,Yj或 X i , Y j − 1 X\_i,Y\_\{j-1\} Xi,Yj−1构成的`LCS`长度相同,它们的`LCS`应该从这两个中选出;如果`dp[i][j]==dp[i-1][j]+1`表明从 X i − 1 , Y j X\_\{i-1\},Y\_j Xi−1,Yj到 X i , Y i X\_i,Y\_i Xi,Yi的`LCS`,`X[i]==Y[j]`,`X[i]`被选中作为`LCS`,然后序列`X`缩短一个单位,去寻找下一个字符;如果`dp[i][j]==dp[i][j-1]+1`说明从 X i , Y j − 1 X\_i,Y\_\{j-1\} Xi,Yj−1转向 X i , Y j X\_i,Y\_j Xi,Yj,`Y[j]`向`LCS`贡献了一个字符,此时的`X[i]`和`Y[j]`是相等的.后面两种情况对应求长度时`X[i]==Y[j]`的情况,但是`dp[i][j]==dp[i-1][j],dp[i][j]==dp[i][j-1],dp[i][j]==dp[i-1][j]+1,dp[i][j]==dp[i]`总是满足其中的两个,所以最后求出的`LCS`一定只是其中的一个可行的方案.

void print_path(const string & a, const string& b){
        
            string ans;
            for (int i = a.length(), j = b.length(); i > 0 && j > 0; ){
        
                if( dp[i][j] == dp[i-1][j]){
        
                    --i;
                }else if( dp[i][j] == dp[i][j-1]){
        
                    --j;
                }else if(dp[i][j] == dp[i-1][j]+1){
        
                    ans += a[i - 1];
                    --i;
                }else{
        
                    ans += b[j - 1];
                    --j;
                }
            }
            reverse(ans.begin(), ans.end());
            cout << ans << endl;
        }

有一点需要注意的是,这样得到的`LCS`序列是一个逆序的,最后要经过一个倒置得到的才是要求的`LCS`的序列.

从上面的`dp`数组可以看出,坐标`i`可以认为表示的是已经处理的序列`X`的长度,`j`表示已经处理的序列`Y`的长度,某一时刻的`dp[i][j]`仅仅和三个状态相关,分别是`dp[i-1][j-1],dp[i-1][j],dp[i][j-1]`,如果列表来看的话,恰好是正上方正左面和左上角的三个方向,而此前的`i-2,i-3,...`很明显则与`i`无关了,所以可以对上面的程序稍加改动,得到一个滚动数组表示的:

void LCS(const string & a, const string& b){
        
            ll ans[2][N] = {
        0};
            int pre = 1, cur = 0;
            for(int i = 1; i <= a.length(); ++i){
        
                swap(cur, pre);
                for (int j = 1; j <= b.length(); ++j){
        
                    if( a[i-1] == b[j-1] )
                        ans[cur][j] = ans[pre][j-1] + 1;
                    else
                        ans[cur][j] = max(ans[cur][j-1], ans[pre][j]);
                }
            }
            printf("%lld\n", ans[cur][b.length()]);
        }

用一个`dp[2][N]`进行滚动,一行表示处理序列`Y`一轮,一个记录的是上轮的结果,一个是当前的结果,没经过依次,交换`cur`和`pre`的值,用这次的覆盖上上次的,最后`cur`哪行的就是最后依次的结果.

## 题目链接 ##

[hdu1159][]

## 题目概述 ##

给出一个序列`X`和序列`Y`,从序列中按下标严格递增( i 1 < i 2 < ⋯ < i k i\_\{1\}<i\_\{2\}<\\cdots<i\_\{k\} i1<i2<⋯<ik)找出一个子序列,这个子序列也是序列`Y`的子序列,即, a i k = b j m , i k − 1 < i k , j m − 1 < j m a\_\{i\_k\}=b\_\{j\_m\},i\_\{k-1\}<i\_k, j\_\{m-1\}<j\_m aik=bjm,ik−1<ik,jm−1<jm,计算这样一个最长的子列的长度.

## 代码实现 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1105;
    ll dp[N][N];
    
    
    void solve(const string & a, const string& b){
        
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= a.length(); ++i){
        
            for(int j = 1;j <= b.length(); ++j){
        
                if(a[i-1] == b[j-1]){
        
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
        
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%lld\n", dp[a.length()][b.length()]);
    }
    
    
    void LCS(const string & a, const string& b){
        
        ll ans[2][N] = {
        0};
        int pre = 1, cur = 0;
        for(int i = 1; i <= a.length(); ++i){
        
            swap(cur, pre);
            for (int j = 1; j <= b.length(); ++j){
        
                if( a[i-1] == b[j-1] )
                    ans[cur][j] = ans[pre][j-1] + 1;
                else
                    ans[cur][j] = max(ans[cur][j-1], ans[pre][j]);
            }
        }
        printf("%lld\n", ans[cur][b.length()]);
    }
    
    void print_path(const string & a, const string& b){
        
        string ans;
        for (int i = a.length(), j = b.length(); i > 0 && j > 0; ){
        
            if( dp[i][j] == dp[i-1][j]){
        
                --i;
            }else if( dp[i][j] == dp[i][j-1]){
        
                --j;
            }else if(dp[i][j] == dp[i-1][j]+1){
        
                ans += a[i - 1];
                --i;
            }else{
        
                ans += b[j - 1];
                --j;
            }
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
    
    int main(int argc, const char** argv) {
        
        string a, b;
        while(cin>>a>>b){
        
            // solve(a, b);
            // print_path(a, b);
            LCS(a, b);
        }
        return 0;
    }

## 其它 ##

[format_png]: /images/20230208/7fee9df32722463abcb448aaf7fba205.png
[hdu1159]: http://acm.hdu.edu.cn/showproblem.php?pid=1159