最長公共子序列

描述

　　一個序列的子序列 (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 }