题目链接
回溯输出解
#include <bits/stdc++.h>
using namespace std;
const int N=;
int dp[N][N],dir[N][N];
char s1[N],s2[N];
int n1,n2;
void m_printf (int x,int y) {
if (x<=||y<=) {
for (int i=;i<=x;i++)
putchar(s1[i]);
for (int i=;i<=y;i++)
putchar(s2[i]);
return ;
}
if (dir[x][y]==) {
m_printf(x-,y-);
putchar (s1[x]);
}
else if (dir[x][y]>) {
m_printf(x-,y);
putchar (s1[x]);
}
else {
m_printf(x,y-);
putchar (s2[y]);
}
return ;
}
int main ()
{
while (~scanf (" %s %s",s1+,s2+)) {
memset (dp,,sizeof(dp));
int n1=strlen(s1+);
int n2=strlen(s2+);
for (int i=;i<=n1;i++)
for (int j=;j<=n2;j++) {
if (s1[i]==s2[j]) {
dir[i][j]=;
dp[i][j]=dp[i-][j-]+;
}
else if (dp[i-][j]>dp[i][j-]) {
dir[i][j]=;
dp[i][j]=dp[i-][j];
}
else {
dir[i][j]=-;
dp[i][j]=dp[i][j-];
}
}
// printf("%d\n",dp[n1][n2]);
m_printf(n1,n2);
printf("\n");
}
return ;
}