最长公共子序列是什么？LCS算法全解析

有志者，事竟成！如果你在学习文章，那么本文《最长公共子序列是什么？LCS算法详解》，就很适合你！文章讲解的知识点主要包括，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

最长公共子序列（LCS）通过动态规划求解，利用dpi表示两字符串前i和前j个字符的LCS长度，当字符匹配时dpi=1+dpi-1，否则dpi=max(dpi-1, dpi)，最终dpm即为所求长度，该方法避免重复计算，时间复杂度O(mn)，适用于diff工具、生物信息学序列比对等场景，且可通过回溯dp表还原具体LCS序列。

最长公共子序列（LCS）指的是在两个或多个给定序列中，所有序列都共有且长度最长的子序列。这里的“子序列”意味着它可以通过删除原序列中的零个或多个元素而得到，但元素的相对顺序不能改变。它不要求在原序列中是连续的，这是它与“最长公共子串”最主要的区别。简单来说，就是找出两个字符串里，那些按顺序排下来都一样，但中间可以有跳过的字符的最长片段。

解决方案

要找出两个字符串的最长公共子序列，最常用且高效的方法是动态规划。这个思路的核心在于，我们将一个大问题拆解成相互关联、且有重叠子问题的小问题来解决。

具体来说，我们可以构建一个二维数组 dp，其中 dp[i][j] 表示字符串 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

初始化： dp[0][j] = 0 （text1 为空时，LCS长度为0） dp[i][0] = 0 （text2 为空时，LCS长度为0）

递推关系： 遍历 text1 的每一个字符 text1[i-1] 和 text2 的每一个字符 text2[j-1]（注意，这里用 i-1 和 j-1 是因为数组索引从0开始，而 dp[i][j] 对应的是前 i 个字符）：

1. 如果 text1[i-1] 等于 text2[j-1]： 这意味着当前字符匹配了，那么LCS的长度就可以在前一个匹配的基础上加1。 dp[i][j] = 1 + dp[i-1][j-1]

2. 如果 text1[i-1] 不等于 text2[j-1]： 当前字符不匹配，LCS的长度取决于两种情况的最大值：

   • text1 的前 i-1 个字符与 text2 的前 j 个字符的LCS长度 (dp[i-1][j])。
   • text1 的前 i 个字符与 text2 的前 j-1 个字符的LCS长度 (dp[i][j-1])。 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

最终，dp[m][n]（其中 m 是 text1 的长度，n 是 text2 的长度）就是两个字符串的最长公共子序列的长度。

为什么动态规划是解决LCS问题的首选？

我个人觉得，动态规划之所以在LCS问题上如此吃香，核心在于它巧妙地规避了重复计算。你想啊，如果不用动态规划，我们可能会尝试用递归来解决。但很快你就会发现，很多子问题的计算结果会被反复用到。比如，计算“ABC”和“ABD”的LCS时，你可能需要知道“AB”和“AB”的LCS；而计算“ABC”和“ACD”的LCS时，可能又会再次需要“AB”和“A”的LCS。这种“重叠子问题”的特性，正是动态规划大展拳脚的地方。

换个角度看，LCS问题还具备“最优子结构”——也就是说，一个问题的最优解可以通过其子问题的最优解来构建。比如，如果你知道 text1 的前 i-1 个字符和 text2 的前 j-1 个字符的LCS，那么结合当前字符的匹配情况，就能直接推导出 text1 的前 i 个字符和 text2 的前 j 个字符的LCS。动态规划正是利用了这两大特性，通过填表的方式，自底向上地解决问题，避免了指数级的计算量，将时间复杂度优化到了 O(mn)，这对于处理较长的字符串来说是至关重要的。相比之下，暴力枚举所有可能的子序列，那简直是天文数字般的计算量，根本不现实。

LCS在实际应用中有哪些具体场景？

LCS虽然听起来有点像个纯粹的算法问题，但它在实际生活和技术领域里，其实扮演着不少关键角色。最直观的，可能就是版本控制系统里的“diff”工具了。当你修改了一段代码，然后想看看和之前的版本有什么不同时，diff 工具就能帮你高亮显示新增、删除或修改的部分。这里面，LCS就在幕后默默工作，它会找出两个文件（或字符串）的最长公共部分，然后那些不属于LCS的，就是被修改或新增的了。这对于代码合并、文件同步都非常有用。

再比如，生物信息学领域，LCS的应用简直是家常便饭。科学家们要分析DNA序列、蛋白质序列的相似性，找出它们之间的演化关系或者功能关联。LCS可以用来衡量两个基因序列的相似度，找出它们共有的基因片段，这对于疾病研究、药物开发都有着深远的意义。

还有，文本编辑器的拼写检查、文本相似度检测（比如论文查重），甚至一些文件同步工具，都会用到LCS的思想。它能帮助我们高效地识别出两个文本块的共同点和差异点，这在很多场景下都是非常基础且重要的能力。说实话，每次看到这些应用，我都会觉得算法的魅力就在于此——它能把一个抽象的数学问题，转化成解决实际痛点的利器。

除了基本长度，如何回溯LCS的具体序列？

知道了LCS的长度，很多时候我们还想知道具体是哪个序列。这就像你知道了考试得了多少分，但更想知道哪些题目做对了。回溯LCS的具体序列，其实就是沿着我们之前构建的 dp 表，从右下角 dp[m][n] 开始，反向推导回去。

它的逻辑是这样的：

1. 从 dp[m][n] 开始，初始化一个空字符串或列表来存储LCS。
2. 如果 text1[i-1] 等于 text2[j-1]： 这说明 text1[i-1]（或 text2[j-1]）是LCS的一部分。我们将这个字符添加到LCS结果中（通常是添加到最前面，因为我们是反向回溯），然后将 i 和 j 都减1，移动到 dp[i-1][j-1]，继续向上左方向回溯。
3. 如果 text1[i-1] 不等于 text2[j-1]： 这时，我们需要看看 dp[i-1][j] 和 dp[i][j-1] 哪个值更大。
   • 如果 dp[i-1][j] > dp[i][j-1]：说明LCS不是由 text2[j-1] 贡献的，我们应该向上移动，将 i 减1，继续在 dp[i-1][j] 处探索。
   • 如果 dp[i][j-1] > dp[i-1][j]：说明LCS不是由 text1[i-1] 贡献的，我们应该向左移动，将 j 减1，继续在 dp[i][j-1] 处探索。
   • 如果 dp[i-1][j] == dp[i][j-1]：这表示两条路径都能得到相同的LCS长度，你可以选择任意一个方向（比如向上移动，即 i 减1），或者如果你想找出所有可能的LCS，这里就需要分叉处理了。但通常我们只找一个。

这个过程一直重复，直到 i 或 j 变为0。最后得到的序列就是LCS。

举个例子： text1 = "ABCBDAB"text2 = "BDCABA"

在构建完 dp 表后，从 dp[7][6] 回溯： 如果 text1[i-1] == text2[j-1]，字符加入LCS，i--, j-- 如果 dp[i-1][j] >= dp[i][j-1]，i-- 否则，j--

通过这样的回溯，你就能把具体的字符序列拼接出来。这个回溯过程虽然看起来有点绕，但它完全依赖于 dp 表中存储的长度信息，非常可靠。

本篇关于《最长公共子序列是什么？LCS算法全解析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！