题解:理解LCS求最长公共子序列的个数的两种情况是怎么回事就可以改动来写这个了。
dp[i][j]得到的方式细分有三种(两种)。左上得到,左边,上边,分别标记就可以了。再用递归查并找输出。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define CLR(a,b) memset(a,b,sizeof(a)) char s1[1010]; char s2[1010]; int dp[1010][1010]; int d[1010][1010]; int l1,l2,i,j; void LCS() { for(i=0;i<=l1;i++) dp[i][0]=0; for(i=0;i<=l2;i++) dp[0][i]=0; for(i=1;i<=l1;i++) { for(j=1;j<=l2;j++) { if(s1[i-1]==s2[j-1]) //字符相等 { dp[i][j]=dp[i-1][j-1]+1; d[i][j]=0; //左上加自己得到 ,标记 0 } else if(dp[i][j-1]<dp[i-1][j]) { dp[i][j]=dp[i-1][j]; //从上面得到 ,标记 1 d[i][j]=1; } else { dp[i][j]=dp[i][j-1]; //从左边得到 ,标记 -1 d[i][j]=-1; } } } } void printf_LCS(int l1,int l2) { if(l1==0||l2==0) return; //递归结束 if(d[l1][l2]==0) { printf_LCS(l1-1,l2-1); //从左上得到,返回左上,结束返回的递归输出左上的字符 printf("%c",s1[l1-1]); } else if(d[l1][l2]==1) printf_LCS(l1-1,l2); //从左边得到,返回左边 else printf_LCS(l1,l2-1); //上边得到,返回上边 } int main() { scanf("%s%s",s1,s2); l1=strlen(s1); l2=strlen(s2); LCS(); //求出最长公共子序列 printf_LCS(l1,l2); //输出~~~ return 0; }