查看“︁最长公共子序列”︁的源代码

[[分类:序列]]
[[分类:动态规划算法实例]]
{{InfoBox
|name=公共子序列
|eng_name=common subsequence
|aliases=公共子列
}}
{{InfoBox
|name=最长公共子序列
|eng_name=longest common subsequence
|aliases=最长公共子列,LCS
}}
'''公共子序列'''('''common subsequence''')，指从一个[[序列]][[集合]]中全部元素（通常为 2 个序列）公共的[[子列]]。

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

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

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

== 算法 ==

=== 原理 ===

两个序列 <math>X,Y</math> 的最长公共子序列 <math>LCS(X,Y)</math> 有以下性质。

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

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

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

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

=== 伪代码 ===

<syntaxhighlight>
过程 最长公共子序列
别名 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
</syntaxhighlight>

=== 时间复杂度 ===

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

因此，总时间复杂度的级别为 <math>O(mn)</math> 。

=== 空间复杂度 ===

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