题目描述
给定两个序列X=
输入
输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。
输出
每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。
示例输入
ABCBDAB BDCABA
示例输出
4
提示
#include <stdio.h> #include <string.h> #define N 200 int main() { int i,j,len1,len2,c[N][N]; char x[N],y[N]; while(gets(x) ) { gets(y); 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]; printf("%d\n",c[len1][len2]); } return 0; }