7-4 sdut-C语言实验-最长公共子序列问题
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
###输入格式:
输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。
###输出格式:
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。
###输入样例:
1. ABCBDAB 2. BDCABA
###输出样例:
4
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include <stdio.h> #include <string.h> #define N 510 int i,j,len1,len2,c[N][N]; char x[N],y[N]; int main() {while(scanf("%s %s",x,y)!=EOF){ len1=strlen(x); len2=strlen(y); for(i=0;i<=len1;i++) {c[i][0]=0;} for(j=0;j<=len2;j++) {c[0][j]=0;} for(i=1;i<=len1;i++){ for(j=1;j<=len2;j++) { if(x[i-1]==y[j-1])//这里一定要注意 { c[i][j]=c[i-1][j-1]+1; } else { if(c[i-1][j]>c[i][j-1]) {c[i][j]=c[i-1][j];} else{ c[i][j]=c[i][j-1];}//max } }} printf("%d\n",c[len1][len2]); } return 0; }
