《算法导论》15.4最长公共子序列（含C++代码）

一、子序列的定义

给定一个序列X = ,对于Z = ，满足如下条件时，就成为X的子序列：存在一个严格递增的X的下标序列，对所有j = 1,2…k满足x_ij = z_j，比如X = ，Y = ，那么就是X和Y的公共子序列，但最长的公共子序列是。

如何解决问题

步骤1：刻画最长公共子序列的特征

步骤2：一个递归解

1、上图意味着，在求X=的一个LCS时，我们需要求解一个或两个子问题。如果x_m=y_n，我们应该求解X_m-1和Y_n-1的一个LCS。将x_m=y_n追加到这个LCS的末尾，就得到X和Y的一个LCS.如果x_m≠y,我们必须求解两个子问题：求X_m-1和Y的一个LCS与X和Y_n-1的一个LCS。两个LCS较长者即为X和Y的一个LCS。
2、我们很容易就看出其中的重叠子问题性质。我们都要求X_m-1和Y_n-1的LCS（可以依据情况在后面进行追加或者是不追加）。
3、用c[i,j]表示X_i和Y_j的LCS的长度。

步骤3：计算LCS的长度

LCS-LENGTH(X,Y)
m = X.length
n = Y.length
let b[1...m,1...n] and c[0...m,0...n] be new tables
for i = 1 to m
	c[i,0] = 0
for j = 0 to n
	c[0,j] = 0
for i = 1 to m
	for j = 1 to n
		if xi = yj
			c[i,j] = c[i-1,j-1] + 1
			b[i,j] = "↖"
		elseif c[i-1,j]>=c[i,j-1]
			c[i,j] = c[i-1,j]
			b[i,j] = "↑"
		else c[i,j]=c[i,j-1]
			b[i,j] = "←"
return c and b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

构造LCS

按照上图给出的箭头，我们就可以追踪到所有的元素。

PRINT-LCS(b,X,i,j)
if i==0 or j==0
	return 
if b[i,j]=="↖"
	PRINT-LCS(b,X,i-1,j-1)
	print xi
elseif b[i,j]=="↑"
	PRINT-LCS(b,X,i-1,j)
else PRINT-LCS(b,X,i,j-1)
1
2
3
4
5
6
7
8
9

C++代码

#include
#include
#define NUM 20
using namespace std;
int c[NUM][NUM];
char b[NUM][NUM];
void LCS_LENGTH(string X, string Y) {
	int m = X.length();
	int n = Y.length();
	for (int i = 1; i <= m; i++) {
		c[i][0] = 0;
	}
	for (int j = 0; j <= n; j++) {
		c[0][j] = 0;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (X[i - 1] == Y[j - 1]) {
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = 'a';
			}
			else if (c[i - 1][j] >= c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
				b[i][j] = 'b';
			}
			else {
				c[i][j] = c[i][j - 1];
				b[i][j] = 'c';
			}
		}
	}
}

void PRINT_LCS(string X, int m, int n)
{
	if (m == 0 || n == 0)
		return;
	if (b[m][n] == 'a') {
		PRINT_LCS(X, m - 1, n - 1);
		cout << X[m - 1];
	}
	else if (b[m][n] == 'b') {
		PRINT_LCS(X, m - 1, n);
	}
	else
		PRINT_LCS(X, m, n - 1);
}

int main()
{
	string X, Y;
	cin >> X >> Y;
	LCS_LENGTH(X, Y);
	PRINT_LCS(X, X.length(), Y.length());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56