最长公共子序列 (Longest Common Subsequence) 是一个经典的动态规划算法, 其有很多实际的应用, 如判别文本相似度, 计算文本 diff 等, 本文讨论最长公共子序列的求解算法

给定两个字符串 X 和 Y, 分别记为 X = <$x_1, x_2, x_3, ... x_k$ > 与 Y = < $y_1, y_2, y_3, ... y_j$ > 以字符串 X 为考察对象, 如果存在由 X 的元素构成的、并按下标严格递增序列 Z = < $x_{i_1}, x_{i_2}, x_{i_3}, ... x_{i_k}$ > 使得 $x_{i_j} = z_j$, 其中 j = 1, 2, ..., k, 则 Z 是 X 的子序列, 同样的也可以得到字符串 Y 的子序列

如果一个序列既是 X 的子序列, 也是 Y 的子序列, 那么该序列称为 X 和 Y 的公共子序列, 公共子序列可能有多个, 例如字符串 X = "abcde" 与字符串 Y = "acde", 它们的公共子序列有 "a", "c", "d", "e", "ac", "ad", "ae", "cd", "ce", "de", "ade", "ace", "cde", "acde", 最长公共子序列问题即是求解两个字符串的所有公共子序列中的最长的那一个, 最长公共子序列可能不唯一, 我们的问题是求解最长公共子序列的长度

暴力算法是计算两个字符串的所有子序列, 然后对两个字符串各自的子序列集合求交集, 最后提取交集中长度最长元素的长度, 对于一个长度为 N 的字符串, 考虑字符串的每一位, 在选取子序列时, 该位可以选择也可以不选择, 每一位都有两种可能, 因此对于长度为 N 的字符串, 其子序列的个数为 $2^N$, 暴力算法遍历字符串 X 的所有子序列, 每次遍历都判断一下当前的子序列是否也是字符串 Y (长度为 M)的子序列, 判断的时间复杂度为 O(m), 因此暴力算法计算最长公共子序列的时间复杂度为 $O(m2^n)$

考虑使用动态规划算法来优化该问题的求解, 关键在于找出 DP 递推关系, 考虑字符串 $X_i$ = <$x_1, x_2, x_3, ... x_i$ > 与 $Y_j$ = < $y_1, y_2, y_3, ... y_j$ >, 假设其最长公共子序列为 $Z_k$ = < $z_1, z_2, z_3,...z_k$ >

• 如果 $x_i = y_j$, 那么一定有 $x_i = y_j = z_k$, 并且 $Z_{k-1}$ 是字符串 $X_{i-1}$ 与字符串 $Y_{j-1}$ 的最长公共子序列

• 如果 $x_i \neq y_j$, $z_k \neq x_i$, 那么 $Z_k$ 是字符串 $X_{i-1}$ 与字符串 $Y_{j}$ 的最长公共子序列

• 如果 $x_i \neq y_j$, $z_k \neq y_j$, 那么 $Z_k$ 是字符串 $X_i$ 与字符串 $Y_{j-1}$ 的最长公共子序列

使用 C[i, j] 表示字符串 $X_i$ 与字符串 $Y_j$ 的最长公共子序列的长度, 根据刚刚的分析, 可以得到如下的递推关系式

$$C[i, j] = \begin{cases} C[i-1, j-1], 其中 x_i = y_j, 且 i, j \gt 0\\ max(C[i-1, j], C[i, j-1]), 其中 x_i \neq y_j, 且 i, j \gt 0\\ \end{cases}$$

递推的初始值

$$C[0, j] = C[i, 0] = 0$$

在上面分析的基础上, 给出 Go 的代码示例:

package main

import "fmt"

func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func MakeDpTable(x, y string) int {
    dpTable := make([][]int, len(x)+1)
    for i := 0; i < len(x)+1; i++ {
        dpTable[i] = make([]int, len(y)+1)
    }
    for i := 1; i < len(x)+1; i++ {
        for j := 1; j < len(y)+1; j++ {
            if x[i-1] == y[j-1] {
                dpTable[i][j] = dpTable[i-1][j-1] + 1
            } else {
                dpTable[i][j] = Max(dpTable[i-1][j], dpTable[i][j-1])
            }
        }
    }
    return dpTable[len(x)][len(y)]
}

func main() {
    x := "abcde"
    y := "acde"
    fmt.Println(MakeDpTable(x, y))
}

最长公共子串是最长公共子序列的特殊情况, 子串要求序列必须是连续的, 在这个约束条件下修改上面的递推关系, 可以得到最长公共子串的递推关系式:

$$C[i, j] = \begin{cases} C[i-1, j-1] + 1, 其中 x_i = y_j, 且 i, j \gt 0\\ 0, 其中 x_i \neq y_j, 且 i, j \gt 0\\ \end{cases}$$

同样地, 递推初始值

$$C[0, j] = C[i, 0] = 0$$

Go 代码示例:

package main

import "fmt"

func MakeDpTable(x, y string) int {
    dpTable := make([][]int, len(x)+1)
    for i := 0; i < len(x)+1; i++ {
        dpTable[i] = make([]int, len(y)+1)
    }
    for i := 1; i < len(x)+1; i++ {
        for j := 1; j < len(y)+1; j++ {
            if x[i-1] == y[j-1] {
                dpTable[i][j] = dpTable[i-1][j-1] + 1
            } else {
                dpTable[i][j] = 0
            }
         }
    }
    return dpTable[len(x)][len(y)]
}

func main() {
    x := "abcde"
    y := "acde"
    fmt.Println(MakeDpTable(x, y))
}