题目链接
回溯输出解
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=107; 4 int dp[N][N],dir[N][N]; 5 char s1[N],s2[N]; 6 int n1,n2; 7 void m_printf (int x,int y) { 8 if (x<=0||y<=0) { 9 for (int i=1;i<=x;i++) 10 putchar(s1[i]); 11 for (int i=1;i<=y;i++) 12 putchar(s2[i]); 13 return ; 14 } 15 if (dir[x][y]==0) { 16 m_printf(x-1,y-1); 17 putchar (s1[x]); 18 } 19 else if (dir[x][y]>0) { 20 m_printf(x-1,y); 21 putchar (s1[x]); 22 } 23 else { 24 m_printf(x,y-1); 25 putchar (s2[y]); 26 } 27 return ; 28 } 29 int main () 30 { 31 while (~scanf (" %s %s",s1+1,s2+1)) { 32 memset (dp,0,sizeof(dp)); 33 int n1=strlen(s1+1); 34 int n2=strlen(s2+1); 35 for (int i=1;i<=n1;i++) 36 for (int j=1;j<=n2;j++) { 37 if (s1[i]==s2[j]) { 38 dir[i][j]=0; 39 dp[i][j]=dp[i-1][j-1]+1; 40 } 41 else if (dp[i-1][j]>dp[i][j-1]) { 42 dir[i][j]=1; 43 dp[i][j]=dp[i-1][j]; 44 } 45 else { 46 dir[i][j]=-1; 47 dp[i][j]=dp[i][j-1]; 48 } 49 } 50 // printf("%d ",dp[n1][n2]); 51 m_printf(n1,n2); 52 printf(" "); 53 } 54 return 0; 55 }