最长公共子序列是一个非常实用的问题，它可以描述两段文本之间的 “相似程度”。所谓的子序列就是从原来的序列中取出一部分做成新的序列，新的序列并不要求是连续的。这和子串有些区别，子串也是原始序列中的一部分，但是该部分必须在原序列中是连续的。

例如：ABCDEFGH，它的子串为 CDEF，当然存在其他的子串。ACGH 在原序列中并不是连续出现的，其被称作原序列的子序列。但是需要注意的是：ACGH 是子序列，CAGH 并不是子序列，即：新序列中的元素的相对位置应该是不变的，原序列中 A 在 C 的左侧，子序列中如果包含 A 和 C 的话，也应该保持 A 在 C 的左侧。

用数学语言描述的话，即：

给定一个序列 \(x = <x_1, x_2 … x_n>\)，给定 x 序列严格递增的下标序列 \(<i_1, i_2 … i_n>\)，如果存在一个序列 \(z = <z_1, z_2 … z_m>\)，使得 \(x_{i_j}=z_{j}\)，此时就说 z 是 x 的一个子序列。

上述描述中严格递增下标序列是为了强调子序列中的元素在原序列中的相对位置保持一致。公共子序列，则是指的最长的同属于 x 和 y 序列的子序列。

1. LCS 思路分析

接下来，我们分析下其算法思路：

假设
序列：\(x = <x_1, x_2 … x_n>\)
序列：\(y = <y_1, y_2 … y_m>\)
LCS： \(z = <z_1, z_2 … z_k>\)

如果 \( x_n = y_m \)，那么 \(x_n = y_m = z_k\)，也就是说 \(x_n=y_m\) 是 LCS 的最后一个元素。

比如：x=BDCABA, y=ABCBDBA，由于 x 和 y 的最后一个字母 A 相同，所以字符 A 必然是 LCS 的最后一个元素，即：LCS 都是啥我还不知道，但是我知道最后一个元素肯定是 A。

如果 \( x_n \neq y_m \)，那么 LCS 需要在 \( x_{n-1} 和 y_m \) 中寻找，或者在 \( x_n 和 y_{n-1} \) 中寻找。

比如：x=BDCABA, y=ABCBDBC，由于 x 和 y 的最后一个字母 A 不相同，此时我们要找 LCS 的话只能在
BDCAB（不包含最后一个字符）和 ABCBDBC，或者 BDCABA 和 ABCBDB（不包含最有一个字符）中寻找。这个两个选项中，LCS 最长的就是我们找的最终的 LCS。

到这里，看似思路都已经 OK 了，但是需要的注意的是，第二种 latex] x_n \neq y_m [/latex] 的情况，需要我们知道 LCS 的长度。因为不知道 LCS 长度的话，接下来我们是在 BDCAB 和 ABCBDBC 情况下寻找 LCS 还是在 BDCABA 和 ABCBDB 情况下寻找 LCS 呢？这显然会让算法无法进行下去。

所以，LCS 算法需要拿到不同序列情况下的公共子序列长度，并将其存储到表中。当我们在计算具体的公共子序列时，也就是碰到上面第二种情况的时候，能够获得长度，从而使得算法能够进行下去。

如何计算任意公共子序列长度呢？这个计算长度是从序列正向遍历，并统计得到。

首先，如果 x 和 y 两个序列中，有一个序列长度为 0，则 LCS 长度肯定为 0。
如果 \(x_i=y_j\)，表示序列 x 第 i 个元素和 y 第 j 个元素相同。此时，LCS 长度必然在原来基础上加 1。
如果 \(x_i \neq y_j\)，那么当前两个序列的 LCS 长度就为以前最大的长度。

到这里了，我们就统计出了不同的两个序列之间的 LCS 长度，此时就可以获得具体的 LCS 序列是什么了。

2. LCS 算法过程

计算 x 和 y 的公共子序列：

x = “BDCABA”
y = “ABCBDAB”

按照前面分析的思路，我们需要得到任意两个 x 与 y 子序列的公共子序列长度。所以，先初始化矩阵，该矩阵将会记录下不同组合的子序列的公共子序列长度，该序列长度为 len + 1，该矩阵我们取名为 c：

      A  B  C  B  D  A  B
   0  0  0  0  0  0  0  0
B  0  0  0  0  0  0  0  0
D  0  0  0  0  0  0  0  0
C  0  0  0  0  0  0  0  0
A  0  0  0  0  0  0  0  0
B  0  0  0  0  0  0  0  0
A  0  0  0  0  0  0  0  0

纵轴为 i, 横轴为 j.

c[i=0][j=0]，表示 x、y 两个序列的长度都为 0，则其 LCS 长度也为 0.
当 c[i=0][j≠0] =0表示 x 长度为 0，j 的长度不为 0，此时其 LCS 长度也为 0；
当 c[i≠0][j=0] =0表示 x 长度不为 0，j 的长度为 0，此时其 LCS 长度也为 0。

按照前面的长度的计算递推公式，我们将会得到如下矩阵：

      A  B  C  B  D  A  B
   0  0  0  0  0  0  0  0
B  0  0  1  1  1  1  1  1
D  0  0  1  1  1  2  2  2
C  0  0  1  2  2  2  2  2
A  0  1  1  2  2  2  3  3
B  0  1  2  2  3  3  3  4
A  0  1  2  2  3  3  4  4

这个矩阵啥意思呢？请看下图：

数字 3 就表示序列 ABCB 和 BDCAB 的 LCS 长度，以此类推就是其他各个数字的含义。得到这个长度的矩阵，我们就可以根据前面思路分析的第一步得到 LCS 序列。

注意：我们是反向遍历 x 和 y 两个序列的，所以得到的输出结果也要反向输出才是最终的正确的 LCS。

3. LCS 算法实现

为了实现简单，我们这里用 Python 而不是 C++ 来实现。

# 计算 LCS 任意两个子序列 LCS 长度
def lcs_length(x, y):

    x_len = len(x) + 1
    y_len = len(y) + 1

    # 初始化矩阵存储 LCS 长度
    c = [[0] * y_len for _ in range(x_len)]

    # 计算不同子序列组合的 LCS 长度
    for i in range(1, x_len):
        for j in range(1, y_len):

            # 由于我们遍历时从1开始，但是原序列的元素是从0开始，故而这里用减1的下标
            if x[i-1] == y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                if c[i-1][j] >= c[i][j-1]:
                    c[i][j] = c[i-1][j];
                else:
                    c[i][j] = c[i][j-1]

    # 返回 LCS 长度矩阵
    return c


result = []


# 计算 x、y 两个序列的 LCS 内容
def lcs(c, x, y, i, j):

    if i == 0 or j == 0:
        return

    if x[i-1] == y[j-1]:

        result.append(x[i-1])
        lcs(c, x, y, i - 1, j - 1)
    else:
        if c[i-1][j] >= c[i][j-1]:
            lcs(c, x, y, i-1, j)
        else:
            lcs(c, x, y, i, j-1)


if __name__ == '__main__':

    x = 'BDCABA'
    y = 'ABCBDAB'

    # 构建 LCS 长度
    c = lcs_length(x, y)
    # 计算 LCS 序列
    lcs(c, x, y, len(x), len(y))
    # 输出 LCS 序列，需要逆序输出
    print(result[::-1])

程序输出结果：

['B', 'D', 'A', 'B']

最长公共子序列（LCS）

1. LCS 思路分析

2. LCS 算法过程

3. LCS 算法实现

文章目录