最长公共子序列Lcs(打印路径)
#include
usingnamespace std;
chara[1010],b[1010];
intdp[1010][1010];
stringstr="";
intpath[1010][1010];//打印路径用,表示(i,j)节点是由那种状态转移过来的voidLcs(inti,int j){
if(i==0||j==0){
return;
}
if(path[i][j]==1){
Lcs(i-1,j-1);
printf("%c",a[i-1]);
}elseif(path[i][j]==2){
Lcs(i-1,j);
}else{
Lcs(i,j-1);
}
return ;
}
int main(){
// freopen("in.txt","r",stdin);scanf("%s%s",a,b);
for(inti=1;i<=strlen(a);i++){
for(intj=1;j<=strlen(b);j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
path[i][j]=1;
}elseif(dp[i-1][j]>dp[i][j-1]){
dp[i][j]=dp[i-1][j];
path[i][j]=2;
}else{
dp[i][j]=dp[i][j-1];
path[i][j]=3;
}
}
}
// cout<<dp[strlen(a+1)][strlen(b+1)]<<endl; Lcs(strlen(a),strlen(b));
cout<<endl;
return0;
}
来源: http://www.bubuko.com/infodetail-2002104.html