这个题目还是挺有意思的就是,难点就是,输出的问题,,
说说步骤,首先应该找到公共序列的i,j坐标,以及本身的值,然后就是遍历str1,如果遇到不是公共序列的i就输出,while循环;
同样的是遍历str2,如果没有遇到公共序列中的j就一直输出,while循环;
这些都输出都结束之后,就可以输出公共序列了.
现在贴出我的代码,,今天下午一直状态不佳,,,诶,,主要是天气太热了点,,烦的要命.
代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> char str1[105],str2[105]; int dp[105][105]; int cnt; struct Node{ int i; int j; char ch; }lc[105]; int max(int a,int b) { return a>=b?a:b; } void LCS(int n,int m) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(str1[i]==str2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } cnt=1; int len=dp[n][m]; if(dp[n][m]==0) return; else { int i=n,j=m; while(len>0) { if(str1[i]==str2[j]) { lc[cnt].i=i; lc[cnt].j=j; lc[cnt].ch=str1[i]; i--,j--; cnt++; len--; } else if(dp[i-1][j]>dp[i][j-1]) i--; else j--; } } } int main() { str1[0]='#'; str2[0]='#'; while(scanf("%s%s",str1+1,str2+1)!=EOF) { int n=strlen(str1+1); int m=strlen(str2+1); LCS(n,m); int i=1,j=1; cnt--; while(i<=n||j<=m) { while(i!=lc[cnt].i&&i<=n) { printf("%c",str1[i]); i++; } while(j!=lc[cnt].j&&j<=m) { printf("%c",str2[j]); j++; } if(cnt>=1) { printf("%c",lc[cnt].ch); i++,j++; cnt--; } } printf("\n"); } return 0; }