思路分析:
在dp LCS的同时记录下状态
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; char str1[105],str2[105]; int dp[105][105],pre[105][105]; void print(int i,int j) { if(!i && !j)return; if(pre[i][j]==0) { print(i-1,j-1); printf("%c",str1[i-1]); } else if(pre[i][j]==1) { print(i-1,j); printf("%c",str1[i-1]); } else { print(i,j-1); printf("%c",str2[j-1]); } } int main() { while(scanf("%s%s",str1,str2)!=EOF) { int len1=strlen(str1); int len2=strlen(str2); memset(dp,0,sizeof dp); for(int i=0;i<=len1;i++) pre[i][0]=1; for(int i=0;i<=len2;i++) pre[0][i]=-1; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; pre[i][j]=0; } else if(dp[i-1][j]>=dp[i][j-1]) { dp[i][j]=dp[i-1][j]; pre[i][j]=1; } else { dp[i][j]=dp[i][j-1]; pre[i][j]=-1; } } print(len1,len2); puts(""); } return 0; }