2620: 动态规划-最长公共子序列
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：3
提交：4
正确率：75.00% 命题人：
题目描述
给定两个序列 $X=${$x_1,x_2,…,x_m$}和 $Y=${$y_1,y_2,…,y_n$}（$0 \le m,n \le 80$），要求找出 $X$ 和 $Y$ 的最长公共子序列 ("$BCBA$"是"$ABCBDAB$"的子序列)。 最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。
测试代码 复制
#include <stdio.h>
#include <string.h>
#define MAXLEN 81
int b[MAXLEN][MAXLEN],c[MAXLEN][MAXLEN]; // c是计算最优值时需要填写的二维表格，b是计算最优解时需要填写的二维表格
void LCSLength(char x[], char y[], int m , int n) {
int i,j,k;
for(i=0; i<=n; i++) c[0][i]=0; //填写第0行数据
for(i=0; i<=m; i++) c[i][0]=0; //填写第0列数据
for(i=1; i<=m; i++) { //分别填写第i行第j列对应的单元格数据
for(j=1; j<= n; j++) {
if(x[i]==y[j]) {
} else if(c[i-1][j]>=c[i][j-1]) {
} else {
}
}
}
}
void LCS(char x[], int i, int j) {
if(i==0 || j==0) return;
if(b[i][j]==1) {
} else if(b[i][j]==2) {
} else {
}
}
int main(void) {
char x[MAXLEN+1],y[MAXLEN+1]; //下标为0的单元不存放有效数据
int m,n;
scanf("%s",x);
m=strlen(x);
scanf("%s",y);
n=strlen(y);
strcpy(x+1,x);
strcpy(y+1,y); //字符串x和y中的字符分别向后移一位，目的是让0号单元不存放有效数据
LCSLength(x,y,m,n);
printf("%d\n",c[m][n]);
LCS(x,m,n);
return 0;
} 输入格式
第一行输入第一个子序列
第二行输入第二个子序列
第二行输入第二个子序列
输出格式
第一行输出最长公共子序列的长度
第二行输出最长公共子序列
第二行输出最长公共子序列
输入样例 复制
ABCBDAB
BDCABA输出样例 复制
4
BCBA提示
如果不用辅助数组b，则函数LCS()如何修改？