最长公共子序列

mac2022-06-30  25

给定两个序列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 源代码)
最新回复(0)