最長公共子序列問題

2019-11-10 17:02:49

字體：大中小

來源：轉載

供稿：網友

PRoblem Description

給定兩個序列X=

Input

輸入數據有多組，每組有兩行，每行為一個長度不超過500的字符串（輸入全是大寫英文字母（A,Z）），表示序列X和Y。

Output

每組輸出一行，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出0。

Example Input

ABCBDABBDCABAExample Output
4Hint
 Author
01 #include<stdio.h>
02 #include<string.h>
03 int max(int a, int b);
04 int main()
05 {
06     char a[555], b[555];
07     int i, n, d[555][555], m, j;
08     while(scanf("%s%s", a, b) != EOF)
09     {
10         memset(d, 0, sizeof(d));
11         n = strlen(a);
12         m = strlen(b);
13         for(i = 1; i <= n; i++)
14         {
15             for(j = 1; j <= m; j++)
16             {
17                 if(a[i-1] == b[j-1])
18                     d[i][j] = d[i-1][j-1] + 1;
19                 else
20                     d[i][j] = max(d[i][j-1], d[i-1][j]);
21             }
22         }
23         printf("%d/n", d[n][m]);
24     }
25     return 0;
26 }
27 int max(int a, int b)
28 {
29     return a > b? a:b;
30 }
31  
 
我舍友的“高級”做法：
01 #include <stdio.h>
02 #include <string.h>
03 int main()
04 {
05     char a[510], b[510];
06     int n, m, c[510][510], i, j;
07     while(~scanf("%s %s", a, b))
08     {
09         memset(c, 0, sizeof(c));
10         n = strlen(a);
11         m = strlen(b);
12         for(j=0; j<m; j++)
13         {
14             if(a[0]==b[j])
15             {
16                 for(i=j; i<m; i++)
17                 {
18                     c[0][i] = 1;
19                 }
20                 break;
21             }
22  
23         }
24         for(j=0; j<n; j++)
25         {
26             if(a[j]==b[0])
27             {
28                 for(i=j; i<n; i++)
29                 {
30                     c[i][0] = 1;
31                 }
32                 break;
33             }
34         }
35         for(i=1; i<n; i++)
36             for(j=1; j<m; j++)
37             {
38                 if(a[i]==b[j])
39                 {
40                     c[i][j] = c[i-1][j-1] + 1;
41                 }
42                 else
43                 {
44                     if(c[i-1][j]>=c[i][j-1])
45                         c[i][j] = c[i-1][j];
46                     else
47                         c[i][j] = c[i][j-1];
48                 }
49             }
50         printf("%d/n", c[n-1][m-1]);
51     }
52     return 0;
53 }