最长公共子序列问题的介绍和求解

曾经终败给现在 2021-09-30 11:24 158阅读 0赞

# 最长公共子序列问题的介绍和求解 #

原文链接：[https://www.techiedelight.com/longest-common-subsequence/][https_www.techiedelight.com_longest-common-subsequence]

最长公共子序列 (longest common subsequence, LCS) 问题就是要找到给定两个字符序列种出现顺序相同的最长子序列的问题，或者说通过删除第一个原始序列中的某些项和删除第二个原始序列中的某些项而得到的相同的最长的子序列。

这个问题不同于找公共字符串的问题，因为子序列并不需要占据原始序列中一片连续的位置。

例如下面的两个字符序列 X 和 Y

X: ABCBDAB

Y: DBCABA

LCS 的长度是 4

LCS 可以是：BDAB，BCAB 和 BCBA

最简单的做法就是检查 \\(X\[1...m\]\\) 的每个子序列，看它是否同样也是 \\(Y\[1...n\]\\) 的子序列。由于 X 的所有可能的子序列有 \\(2^\{m\}\\) 个，所以这种解决方法的复杂度是 \\(O(n\*2^\{m\})\\)。

LCS 问题有 [optimal substructure][]，这意味着该问题可以被分解成更小的，简单的"子问题"，而这些问题又可以继续分解成更加简单的子问题，直到最后问题变得平凡。

1.  以长度为 m 的序列 \\(X\\) 和 长度为 n 的子序列 \\(Y\\)为例，这里假定它们以相同的元素结尾。
    
    为了找到它们的 LCS，可以通过移除最后一个元素来减少每个序列的长度，然后找到缩短后的序列的 LCS，然后将找到的 LCS 追加移除的元素。所以我们可以得到结论：
    
    \\\[LCS(X\[1..m\], Y\[1..n\]) = LCS(X\[1..m-1\], Y\[1..n-1\]) + X\[m\] \\qquad if \\; X\[m\] = Y\[n\]\\\]
2.  现在假设这两个序列结尾的字符并不相同。
    
    那么 \\(X\\) 和 \\(Y\\) 的 LCS 则是 \\(LCS(X\[1..m-1\], Y\[1..n\])\\) 和 \\(LCS(X\[1..m\], Y\[1..n-1\])\\) 中较长的那个。为了理解这个性质，我们可以以下面两个序列为例：
    
    X: ABCBDAB *(n elements)*
    
    Y: BDCABA *(m elements)*
    
    这两个序列的 LCS 要么以 B 结尾（序列 \\(X\\) 的最后一个字符），要么不是。
    
    **Case 1**:

转载于:https://www.cnblogs.com/tuhooo/p/10882127.html

[https_www.techiedelight.com_longest-common-subsequence]: https://www.techiedelight.com/longest-common-subsequence/
[optimal substructure]: https://www.techiedelight.com/introduction-dynamic-programming/?v=1#optimal-substructure