Longest Common Subsequence (最長共通部分列)
(DP/LongestCommonSubsequence.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "DP/LongestCommonSubsequence.hpp"

概要

最長共通部分列を求める．復元して返す．

計算量

列A, 列Bに対し，O ( |A| * |B| )

Verified with

• test/AOJ_ALDS1_10_c.test.cpp

Code

template<typename S>
S LongestCommonSubsequence(S a,S b){
    int n=(int)a.size(),m=(int)b.size();
    vector<vector<int>> dp(n+1,vector<int>(m+1,0)),pre(n+1,vector<int>(m+1,-1));
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
        if(i<n and j<m and a[i]==b[j]){
            if(chmax(dp[i+1][j+1],dp[i][j]+1)) pre[i+1][j+1]=1;
        }
        if(i<n)if(chmax(dp[i+1][j],dp[i][j])) pre[i+1][j]=2;
        if(j<m)if(chmax(dp[i][j+1],dp[i][j])) pre[i][j+1]=3;
    }

    S ret;
    int i=n,j=m;
    while(i and j and pre[i][j]>0){
        if(pre[i][j]==1){
            i--,j--;
            ret.push_back(a[i]);
        }
        else if(pre[i][j]==2) i--;
        else if(pre[i][j]==3) j--;
    }

    reverse(begin(ret),end(ret));
    return ret;
}

#line 1 "DP/LongestCommonSubsequence.hpp"
template<typename S>
S LongestCommonSubsequence(S a,S b){
    int n=(int)a.size(),m=(int)b.size();
    vector<vector<int>> dp(n+1,vector<int>(m+1,0)),pre(n+1,vector<int>(m+1,-1));
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
        if(i<n and j<m and a[i]==b[j]){
            if(chmax(dp[i+1][j+1],dp[i][j]+1)) pre[i+1][j+1]=1;
        }
        if(i<n)if(chmax(dp[i+1][j],dp[i][j])) pre[i+1][j]=2;
        if(j<m)if(chmax(dp[i][j+1],dp[i][j])) pre[i][j+1]=3;
    }

    S ret;
    int i=n,j=m;
    while(i and j and pre[i][j]>0){
        if(pre[i][j]==1){
            i--,j--;
            ret.push_back(a[i]);
        }
        else if(pre[i][j]==2) i--;
        else if(pre[i][j]==3) j--;
    }

    reverse(begin(ret),end(ret));
    return ret;
}

Back to top page