最长公共子序列

公共子序列
术语名称	公共子序列
英语名称	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] 两个变量，进行一个二维的动态规划。