给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。
比如两个串为:
abcicba
abdkscab
ab是两个串的子序列,abc也是,abca也是,其中abca是这两个字符串最长的子序列。
Input
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)
Output
输出最长的子序列,如果有多个,随意输出1个。
Input示例
abcicba
abdkscab
Output示例
abca
#include <bits/stdc++.h>
using namespace std;
char a[],b[];
int dp[][];
string str="";
int path[][];//打印路径用,表示(i,j)节点是由那种状态转移过来的
void Lcs(int i,int j){
if(i==||j==){
return;
}
if(path[i][j]==){
Lcs(i-,j-);
printf("%c",a[i-]);
}else if(path[i][j]==){
Lcs(i-,j);
}else{
Lcs(i,j-);
}
return ;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%s%s",a,b);
for(int i=;i<=strlen(a);i++){
for(int j=;j<=strlen(b);j++){
if(a[i-]==b[j-]){
dp[i][j]=dp[i-][j-]+;
path[i][j]=;
}else if(dp[i-][j]>dp[i][j-]){
dp[i][j]=dp[i-][j];
path[i][j]=;
}else{
dp[i][j]=dp[i][j-];
path[i][j]=;
}
}
}
// cout<<dp[strlen(a+1)][strlen(b+1)]<<endl;
Lcs(strlen(a),strlen(b));
cout<<endl;
return ;
}