d231. 97北縣賽-2-基因序列密碼問題 -- 97學年度北基區資訊學科能力競賽 | From: [118.170.105.86] | 發表日期 : 2023-07-25 21:27

#include<bits/stdc++.h>

using namespace std;

 

int main()

{

int x,y;

string a,b;

cin>>a>>b;

int dp[55][55];

 

x = a.length();

y = b.length();

 

for(int i=0;i<=x;i++) dp[i][0] = 0;

for(int i=1;i<=y;i++) dp[0][i] = 0;

 

 

vector<string>be(55,""),af(55,"");

for(int i=1;i<=x;i++){

for(int j=1;j<=y;j++){

if(a[i-1] == b[j-1]){

dp[i][j] = dp[i-1][j-1] + 1;

af[j] = be [j-1] + a[i-1];

}else{

if(dp[i-1][j]<dp[i][j-1]){

dp[i][j] = dp[i][j-1];

af[j] = af[j-1];

}else{

dp[i][j] = dp[i-1][j];

af[j] = be[j];

}

 

}

}

be = af;

}

cout<<af[y]<<endl;

/*

for(int i=0;i<=x;i++){

for(int j=0;j<=y;j++) printf("%d ",dp[i][j]);

printf("\n");

}*/

}