Data Structures Algorithms 简明教程
Longest Common Subsequence Algorithm
最长公共子序列问题是找到两个给定字符串中都存在的最长序列。
但在我们理解这个问题之前，我们先来理解一下什么是子序列 -
假设我们有一个序列 S = <s1, s2, s3, s4, …,sn>。并且另一个序列 Z = <z1, z2, z3, …,zm> 在 S 上被称为 S 的子序列，当且仅当它可以通过删除 S 中的某些元素而生成。简单来说，一个子序列是由构成序列中一个小部分的连续元素组成的。
Naive Method
令 X 是长度为 m 的序列， Y 是长度为 n 的序列。检查 X 的每一个子序列是否都是 Y 的子序列，并返回找到的最长公共子序列。
X 中有 2m 个子序列。测试序列是否为 Y 的子序列需要 O(n) 的时间。因此，朴素算法将需要 O(n2m) 的时间。
Longest Common Subsequence Algorithm
令 X=<x1,x2,x3….,xm> 和 Y=<y1,y2,y3….,ym> 为序列。要计算一个元素的长度，可以使用以下算法。
Step 1 - 构造一个大小为 n × m 的空邻接表，其中 n = 序列 X 的大小，m = 序列 Y 的大小。表中的行表示序列 X 中的元素，列表示序列 Y 中的元素。
Step 2 - 第 0 行和列必须用零填充。剩下的值根据不同的情况填充，通过维护一个计数器值。
-
Case 1 - 如果计数器在 X 和 Y 序列中遇到公共元素，则将计数器加 1。
-
Case 2 - 如果计数器在 T[i, j] 中没有在 X 和 Y 序列中遇到公共元素，则在 T[i-1, j] 和 T[i, j-1] 之间找到最大值来填充 T[i, j]。
Step 3 - 填充表格后，从表格中的最后一个值回溯。此处的回溯通过跟踪计数器首先增量的位置来完成。
Step 4 - 最长的公共子序列是通过记录跟踪路径中的元素而获得的。
Pseudocode
在此过程中，表 C[m, n] 以行优先顺序计算，另一个表 B[m,n] 计算用于构造最优解。
Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X)
n := length(Y)
for i = 1 to m do
C[i, 0] := 0
for j = 1 to n do
C[0, j] := 0
for i = 1 to m do
for j = 1 to n do
if xi = yj
C[i, j] := C[i - 1, j - 1] + 1
B[i, j] := ‘D’
else
if C[i -1, j] ≥ C[i, j -1]
C[i, j] := C[i - 1, j] + 1
B[i, j] := ‘U’
else
C[i, j] := C[i, j - 1] + 1
B[i, j] := ‘L’
return C and BAlgorithm: Print-LCS (B, X, i, j)
if i=0 and j=0
return
if B[i, j] = ‘D’
Print-LCS(B, X, i-1, j-1)
Print(xi)
else if B[i, j] = ‘U’
Print-LCS(B, X, i-1, j)
else
Print-LCS(B, X, i, j-1)此算法将打印 X 和 Y 的最长公共子序列。
