描述
一個序列的子序列 (subsequence) 是指在該序列中刪去若干(可以為 0 個)元素後得到的序列。准確的說,若給定序列 X = (x1 , x2 , · · · , xm ),則另一個序列 Z = (z1 , z2 , · · · , zk ),是 X 的子序列是指存在一個嚴格遞增下標序列 (i1 , i2 , · · · , ik ) 使得對於所有 j = 1, 2, · · · , k有 zj = xij 。例如,序列 Z = (B, C, D, B) 是序列 X = (A, B, C, B, D, A, B) 的子序列,相應的遞增下標序列為 (1, 2, 4, 6)。給定兩個序列 X 和 Y,求 X 和 Y 的最長公共子序列 (longest common subsequence)。
輸入
輸入包括多組測試數據,每組數據占一行,包含兩個字符串(字符串長度不超過 200),代表兩個序列。兩個字符串之間由若干個空格隔開。
輸出
對每組測試數據,輸出最大公共子序列的長度,每組一行。
樣例輸入
abcfbc abfcab
programming contest
abcd mnp
樣例輸出
4
2
0
分析
最長公共子序列問題具有最優子結構性質。設序列 X = (x1 , x2 , · · · , xm ) 和 Y = (y1 , y2 , · · · , yn ) 的最長公共子序列為 Z = (z1 , z2 , · · · , zk ),則
• 若 xm = yn ,則 zk = xm = yn ,且 Zk−1 是 Xm−1 和 Yn−1 的最長公共子序列。
• 若 xm ≠ yn 且 zk ≠ xm ,則 Z 是 Xm−1 和 Y 的最長公共子序列。
• 若 xm ≠ yn 且 zk ≠ yn ,則 Z 是 X 和 Yn−1 的最長公共子序列。
其中,Xm−1 = (x1 , x2 , · · · , xm−1 ), Yn−1 = (y1 , y2 , · · · , yn−1 ), Zk−1 = (z1 , z2 , · · · , zk−1 )。
設狀態為 d[i][j],表示序列 Xi 和 Yj 的最長公共子序列的長度。由最優子結構可得狀
態轉移方程如下:
0 i = 0, j = 0
d[i][j] = { d[i − 1][j − 1] + 1 i, j > 0; xi = yi
max {d[i][j − 1], d[i − 1][j]} i, j > 0; xi ≠ yi
如果要打印出最長公共子序列,需要另設一個數組 p,p[i][j] 記錄 d[i][j] 是由哪個子問題得到的。
實現代碼
1 #include <stdio.h>
2 #include <string.h>
3 #define MAX 201
4 /* 字符串最大長度為 200 */
5
6 int d[MAX][MAX]; /* d[i][j] 表示序列 Xi 和 Yj 的最長公共子序列的長度 */
7 char x[MAX], y[MAX]; /* 字符串末尾有個'0' */
8
9 void lcs(const char *x, const int m, const char *y, const int n)
10 {
11 int i, j;
12 for (i = 0; i <= m; i++)
13 d[i][0] = 0;
14 for (j = 0; j <= n; j++)
15 d[0][j] = 0;
16
17 /* 邊界初始化 */
18 for (i = 1; i <= m; i++)
19 {
20 for (j = 1; j <= n; j++)
21 {
22 if (x[i-1] == y[j-1])
23 {
24 d[i][j] = d[i-1][j-1] + 1;
25 } else {
26 d[i][j] = d[i-1][j] > d[i][j-1] ? d[i-1][j] : d[i][j-1];
27 }
28 }
29 }
30 }
31
32 void lcs_extend(const char *x, const int m, const char *y, const int n);
33 void lcs_print(const char *x, const int m, const char *y, const int n);
34
35 int main()
36 {
37 while (scanf ("%s%s", x, y) != EOF)
38 {
39 const int lx = strlen(x);
40 const int ly = strlen(y);
41 lcs(x, lx, y, ly);
42 printf ("%d\n", d[lx][ly]);
43 }
44 return 0;
45 }
46
47 int p[MAX][MAX]; /* p[i][j] 記錄 d[i][j] 是由哪個子問題得到的 */
48 void lcs_extend(const char *x, const int m, const char *y, const int n)
49 {
50 int i, j;
51 memset(p, 0, sizeof(p));
52 for (i = 0; i <= m; i++)
53 d[i][0] = 0;
54 for (j = 0; j <= n; j++)
55 d[0][j] = 0;
56
57 /* 邊界初始化 */
58 for (i = 1; i <= m; i++)
59 {
60 for (j = 1; j <= n; j++)
61 {
62 if (x[i-1] == y[j-1])
63 {
64 d[i][j] = d[i-1][j-1] + 1;
65 p[i][j] = 1;
66 }
67 else
68 {
69 if (d[i-1][j] >= d[i][j-1])
70 {
71 d[i][j] = d[i-1][j];
72 p[i][j] = 2;
73 }
74 else
75 {
76 d[i][j] = d[i][j-1];
77 p[i][j] = 3;
78 }
79 }
80 }
81 }
82 }
83
84 void lcs_print(const char *x, const int m, const char *y, const int n)
85 {
86 if (m == 0 || n == 0)
87 return;
88 if (p[m][n] == 1)
89 {
90 lcs_print(x, m - 1, y, n - 1);
91 printf("%c", x[m - 1]);
92 }
93 else if (p[m][n] == 2)
94 {
95 lcs_print(x, m - 1, y, n);
96 }
97 else
98 {
99 lcs_print(x, m, y, n - 1);
100 }
101 }
