本文共 2095 字，大约阅读时间需要 6 分钟。
#include #include #include #include using namespace std;#define MAXN 111int dp[MAXN][MAXN];char str1[MAXN],str2[MAXN];int mark[MAXN];int path[MAXN][MAXN];int len1,len2;int main(){ while(~scanf("%s%s",str1,str2)){ len1=strlen(str1); len2=strlen(str2); memset(dp,0,sizeof(dp)); memset(path,0,sizeof(path)); memset(mark,-1,sizeof(mark)); 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; }else if(dp[i-1][j]>dp[i][j-1]){ dp[i][j]=dp[i-1][j]; path[i][j]=1; }else { dp[i][j]=dp[i][j-1]; path[i][j]=2; } } } for(int i=len1,j=len2;i>=1&&j>=1;){ if(path[i][j]==0){ i--,j--; mark[i]=j; }else if(path[i][j]==1){ i--; }else j--; } int k=0; for(int i=0;i #include #define size 201int Max(int x,int y){return x>y?x:y;}struct rem {int i,j;/*i记录主串位置，j记录副串当前字符位置*/char ch;/*记录当前字符*/};char a[size],b[size];int dp[size][size];rem ans[size];int len;/*指示ans的长度*/void lcs(int m,int n){int i,j;memset(dp,0,sizeof(dp));len = 0;for (i=1;i<=m;i++){for (j=1;j<=n;j++){if(a[i]==b[j])dp[i][j] = dp[i-1][j-1]+1;elsedp[i][j] = Max(dp[i-1][j],dp[i][j-1]);}}if(dp[m][n] == 0)/*如果没有公共序列，直接输出*/printf("%s%s",a,b);else{/*取出最长公共子序列的字母*/i = m,j = n;while (i!=0&&j!=0){if ((dp[i][j] = dp[i-1][j-1]+1)&&a[i] == b[j]){ans[len].i = i;ans[len].j = j;ans[len++].ch = a[i];/*倒序保存最长公共子序列字母*/i--,j--;}else if(dp[i-1][j]>dp[i][j-1])i--;elsej--;}/*取出最长公共子序列的字母*/}}int main(){int a1,b1,i,j,k;while (scanf("%s%s",a+1,b+1)!=EOF){a1 = strlen(a+1);b1 = strlen(b+1);lcs(a1,b1);i = j = 1;for (k=len-1;k>=0;k--){while (i!=ans[k].i){printf("%c",a[i]);i++;}while (j!=ans[k].j){printf("%c",b[j]);j++;}printf("%c",ans[k].ch);i++,j++;}printf("%s%s/n",a+ans[0].i+1,b+ans[0].j+1);}return 0;}
转载地址：http://kjbci.baihongyu.com/