最长公共子序列
子序列 (Subsequence): 由序列中若干字符, 按原相对次序构成
最长公共子序列 (Longest Common Subsequence): 两个序列公共子序列中的最长者
LCS(): 递归
对于序列 A[0, n] 和 B[0, m], LCS(A, B) 有三种情况
-
递归基: 若
n = -1或m = -1, 则取作空序列 (“”) -
减而治之: 若
A[n] = 'X' = B[m], 则取作LCS(A[0, n), B[0, m)) + 'X'
- 分而治之: 若
A[n] ≠ B[m], 则在LCS(A[0, n], B[0, m))与LCS(A[0, n), B[0, m])中取更长者
LCS(): 理解
-
单调性: 无论如何, 每经过一次比对, 原问题的规模必可减小。
具体的, 作为输入的两个序列, 至少其一的长度缩短一个单位。
-
最好情况 (不出现分而治之的情况) 下, 只需
O(n+m)时间。但问题在于, 出现分而治之的情况下, 原问题将被分解为两个子问题。
更糟糕的是, 它们在随后进一步导出的子问题, 可能雷同。
在最坏情况下,
\[\begin{pmatrix} & n + m - a - b & \\ & n - a & \end{pmatrix} = \begin{pmatrix} & n + m - a - b & \\ & m - a & \end{pmatrix}\]LCS(A[0, a], B[0, b])出现的次数为特别的,
\[\begin{pmatrix} & n + m & \\ & n & \end{pmatrix} = \begin{pmatrix} & n + m & \\ & m & \end{pmatrix}\]LCS(A[0], B[0])的次数可多达:当 n = m 时, 时间复杂度为 $ O(2^n) $
LCS(): 迭代
与 fib() 类似, LCS() 递归版也有大量重复的递归实例 (子问题), (最坏情况下) 先后共计出现 $ O(x^n) $ 个
各子问题, 分别对应于 A 和 B 的某个前缀组合, 因此总共不过 $ O(n * m) $ 种
采用动态规划的策略, 只需要 $ O(n * m) $ 时间可计算出所有子问题
为此, 只需:
-
将所有子问题 (假想地) 列成一张表
-
颠倒计算方向, 从
LCS(A[0], B[0])出发依次计算出所有项
算法实现
算法实现请看: 《PHP — LCS》
【注】虽然是用 PHP 实现, 但原理基本一致, 可做参考
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
