AcWing 315 Trip

bhqjwdsdsg · 2020-02-02 16:32:27 · 个人记录

题意：给定两个字符串a和b，求这两个字符串的LCS（最长公共子序列），要求输出方案。

思路：DP求出LCS长度，递归输出方案。求LCS长度：状态：dp[i][j]，表示a的前i位和b的前j位的LCS长度；转移方程：若a[i]==b[j]则dp[i][j]=dp[i-1][j-1]+1，否则dp[i][j]=max{dp[i][j], dp[i-1][j], dp[i][j-1]}。输出方案：维护pos1和pos2数组，pos1[i][j]表示a的第i位及第i位之后第一次出现字母j的位置，pos2同理，倒序维护可在递归过程中直接输出答案；递归：dfs(len,lena,lenb)，表示公共子序列当前长度为len，该子序列在a的前lena位，b的前lenb位。参考：poj1934 Trip【线性DP】【输出方案】

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
string a,b;
int len1,len2;
int dp[85][85];
int pos1[85][26],pos2[85][26];
string res;
void dfs(int len,int lena,int lenb){
    if(len==dp[len1][len2]+1){
        for(int i=0;i<dp[len1][len2];i++) cout<<res[i];cout<<endl;
        return ;
    }
    if(lena>len1 || lenb>len2) return ;
    for(int i=0;i<26;i++){
        int t1=pos1[lena][i];
        int t2=pos2[lenb][i];
        if(dp[t1][t2]==len){
            res[len-1]=char(i+'a');
            dfs(len+1,t1+1,t2+1);
        }
    }
    return ;
}
int main(){
    cin>>a>>b;
    len1=a.length();
    len2=b.length();
    a=" "+a;
    b=" "+b;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
            else{
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
        }
    }
    for(int i=len1;i>=1;i--){
        for(int j=0;j<26;j++){
            if(a[i]==j+'a') pos1[i][j]=i;
            else pos1[i][j]=pos1[i+1][j];
        }
    }
    for(int i=len2;i>=1;i--){
        for(int j=0;j<26;j++){
            if(b[i]==j+'a') pos2[i][j]=i;
            else pos2[i][j]=pos2[i+1][j];
        }
    }
    dfs(1,1,1);
    return 0;
}