最长公共子序列

来自GSXAB的知识库
公共子序列
术语名称 公共子序列
英语名称 common subsequence
别名 公共子列
最长公共子序列
术语名称 最长公共子序列
英语名称 longest common subsequence
别名 最长公共子列, LCS

公共子序列(common subsequence)，指从一个序列集合中全部元素（通常为 2 个序列）公共的子列。

最长公共子序列(longest common subsequence, 缩写 LCS)，指从这样集合中全部元素全部公共子列中的最长者。

字符（或其他符号）序列的最长公共子序列是一个经典算法问题。在序列数目任意时，是一个 NP-难问题。当序列数目有限时，可以在多项式时间内通过线性规划方式解决。

本文的主题是“最长公共子序列(longest common subsequence, LCS)问题”而不是“最长公共子串(longest common substring, LCS)问题”。

算法

原理

两个序列 [math]\displaystyle{ X,Y }[/math] 的最长公共子序列 [math]\displaystyle{ LCS(X,Y) }[/math] 有以下性质。

  • 对于某个符号 [math]\displaystyle{ a }[/math] ，通过连接构成序列 [math]\displaystyle{ Xa,Ya }[/math] 必然有 [math]\displaystyle{ LCS(Xa,Ya)=LCS(X,Y)a }[/math] 。可以推广到相同后缀序列。
  • 对于不同的两个符号 [math]\displaystyle{ x\neq y }[/math] ，连接起来的序列 [math]\displaystyle{ Xx,Yy }[/math] 要么其中一个新符号进入公共子序列，要么不起作用，必然有 [math]\displaystyle{ LCS(Xx,Yy)=\max\{LCS(Xx,Y), LCS(X,Yy)\} }[/math] 。

因此记每个序列 [math]\displaystyle{ X }[/math] 的第 [math]\displaystyle{ n }[/math] 项为 [math]\displaystyle{ x_n }[/math] ，前 [math]\displaystyle{ n }[/math] 项为 [math]\displaystyle{ X_n }[/math] ，则可以获得 LCS 函数的递推形式：

[math]\displaystyle{ LCS(X_i,Y_j) = \begin{cases} \varepsilon &, ij=0 \\ LCS(X_{i-1},Y_{j-1})x_i &, i\gt 0,j\gt 0,x_i=y_i \\ \max\{LCS(X_i,Y_{j-1}), LCS(X_{i-1},Y_j)\} &, i\gt 0,j\gt 0,x_i\neq y_i \\ \end{cases} }[/math]

因此算法可以根据 [math]\displaystyle{ LCS(X_0,Y_0)=\varepsilon }[/math] 的初始状态与 [math]\displaystyle{ i,j }[/math] 两个变量，进行一个二维的动态规划。

伪代码

过程 最长公共子序列
别名 longest_common_subsequence
参数 X, Y : 对象的列表 // 输入的两个序列
返回 : 对象的列表 // 最长公共子序列

令 m ← X的长度, n ← Y的长度
创建 dp[0..m][0..n] : 整数的二维表 // 动态规划表
创建 trace[0..m][0..n] : 枚举【↖、↑、←】的二维表 // 回溯路径表

循环 i ← 0 到 m
    令 dpᵢ,₀ ← 0
循环 j ← 0 到 n
    令 dp₀,ⱼ ← 0

循环 i ← 1 到 m
    循环 j ← 1 到 n
        如果 xᵢ₋₁ = yⱼ₋₁ 那么
            令 dpᵢ,ⱼ ← dpᵢ₋₁,ⱼ₋₁ + 1
            令 traceᵢ,ⱼ ← "↖" // 匹配成功，当前下标为当前最长公共子序列的新元素，指向左上
        否则
            如果 dpᵢ₋₁,ⱼ ≥ dpᵢ,ⱼ₋₁ 那么
                令 dpᵢ,ⱼ ← dpᵢ₋₁,ⱼ
                令 traceᵢ,ⱼ ← "↑"  // 当前最长公共子序列来自上方值
            否则
                令 dpᵢ,ⱼ ← dpᵢ,ⱼ₋₁
                令 traceᵢ,ⱼ ← "←"  // 当前最长公共子序列来自左方值

// 此时 dpₘ,ₙ 和 traceₘ,ₙ 处即为最后的公共子序列长度和链表方向

令 lcs ← 空列表
令 i ← m, j ← n
当 i > 0 且 j > 0 时
执行
    如果 traceᵢ,ⱼ == "↖" 那么
        将 xᵢ₋₁ 插入 lcs 开头
        令 i ← i-1, j ← j-1
    否则如果 traceᵢ,ⱼ == "↑" 那么
        令 i ← i-1
    否则
        令 j ← j-1

返回 lcs

时间复杂度

算法分为三部分：

  1. 初始化动态规划表和回溯表：需要初始化两个二维数组，大小为 [math]\displaystyle{ (m+1)(n+1) }[/math] 。且需要额外 [math]\displaystyle{ (m+1+n+1) }[/math] 次边界条件赋值，赋值次数为 [math]\displaystyle{ O(m+n) }[/math] 。
  2. 填充动态规划表和回溯表：这部分有双重循环，外层循环m次，内层循环n次，因此时间复杂度为 [math]\displaystyle{ O(mn) }[/math] 。
  3. 回溯构建：回溯过程从右下角开始向上向左到边缘，最坏情况下需要回溯到左上角，即移动 [math]\displaystyle{ (m+n) }[/math] 步，因此时间复杂度为 [math]\displaystyle{ O(m+n) }[/math] 。

因此，总时间复杂度的级别为 [math]\displaystyle{ O(mn) }[/math] 。

空间复杂度

除了返回值本身以外，额外的空间复杂度包括两个大小为 [math]\displaystyle{ (m+1)(n+1) }[/math] 的二维表，因此有 [math]\displaystyle{ O(mn) }[/math] 的空间复杂度。

检索自“https://knowledge.gsxab.top/index.php?title=最长公共子序列&oldid=4585”