给定两个序列X=
输入
输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。
输出
每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。
示例输入
ABCBDAB
BDCABA
示例输出
4
1 #include<stdio.h>
2 #include<
string.h>
3 int main ()
4 {
5 char s1[
510], s2[
510];
6 int i,j,maxsum[
510][
510];
7 while(gets(s1))
8 {
9 gets(s2);
10 int len1 =
strlen(s1);
11 int len2 =
strlen(s2);
12 memset(maxsum,
0,
sizeof(maxsum));
13 for(i =
1; i <= len1; i++
)
14 for(j =
1; j <= len2; j++
)
15 {
16 if(s1[i-
1] == s2[j-
1])
17 maxsum[i][j] = maxsum[i-
1][j-
1] +
1;
18 else
19 {
20 if(maxsum[i-
1][j] > maxsum[i][j-
1])
21 maxsum[i][j] = maxsum[i-
1][j];
22 else maxsum[i][j] = maxsum[i][j-
1];
23 }
24 }
25 printf(
"%d\n",maxsum[len1][len2]);
26 }
27 return 0;
28 }
29
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/23/3038827.html
相关资源:最长公共子序列(C 源代码)