最长公共子序列是什么？LCS的求解方法

· 日常编程 · 11245

最长公共子序列（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的求解方法的详细内容，更多请关注骃骐网【www.myinqi.com】。

相关推荐：

高效求解含零块的分块对角矩阵伪逆（保持零块不变）

本文介绍一种针对大规模分块对角矩阵的高效逆运算方法：仅对非零3×3对角块求逆，保留零块为零，避免全矩阵求逆开销，时间复杂度降至o(n)，适用于n≈10⁴量级的稀疏块结构。 本文介绍一种针对大规模分块对角矩阵的高效逆运算方法：仅对非零3×3对角块求逆，保留零块为零，避免全矩阵求逆开销，时间复杂度降至o(n)，适用于n≈10⁴量级的稀疏块结构。 在科学计算与算子建模中，常遇到结构化的大规模矩阵——尤其...

如何高效求解含零块的分块对角矩阵的伪逆（保持零块不变）

本文介绍一种针对大规模分块对角矩阵的高效逆运算方法：仅对非零3×3对角块求逆，跳过零块并保持其为零，避免全矩阵运算，时间复杂度降至o(n)，适用于n≈10⁴量级场景。 本文介绍一种针对大规模分块对角矩阵的高效逆运算方法：仅对非零3×3对角块求逆，跳过零块并保持其为零，避免全矩阵运算，时间复杂度降至o(n)，适用于n≈10⁴量级场景。 在科学计算与算子建模中，常遇到结构稀疏的分块对角矩阵——例如由物...

如何在 Python 中高效求解模 2 下的行向量线性相关关系

本文介绍使用 galois 库在有限域 gf(2) 上快速计算矩阵零空间，从而自动找出使行向量线性组合模 2 为零的一组非零系数，避免手动实现高斯消元。 本文介绍使用 galois 库在有限域 gf(2) 上快速计算矩阵零空间，从而自动找出使行向量线性组合模 2 为零的一组非零系数，避免手动实现高斯消元。 在密码学、编码理论和布尔函数分析等场景中，常需判断一组整数向量在模 2 意义下是否线性相关，...

如何用Python TensorFlow实现时间序列预测_通过LSTM窗口切片解决

直接用tf.keras.layers.LSTM预测时间序列输出全零或震荡严重，是因为默认return_sequences=False导致模型只输出末步状态，而时间序列预测需滑动窗口对齐输入与标签；解决关键是手动构造X_train和y_train，确保窗口不越界、维度正确、时序因果性不被破坏。 为什么直接用 tf.keras.layers.LSTM 预测时间序列会输出全零或震荡严重？ 因为 LSTM...

如何使用Python的zip函数并行迭代多个序列_利用zip将其打包为元组对

zip是“最短截断”惰性迭代器，任一输入耗尽即停止，返回单次可用的zip对象；解包zip(*)可反向拆分，但结果为元组。 Python 的 zip 函数不是“打包成元组对”，而是把多个可迭代对象的对应位置元素组合成元组，生成一个惰性迭代器；一旦某个输入耗尽，zip 立即停止——这是它最常被误用也最容易出 bug 的地方。 为什么 for 循环里用 zip 有时少了一轮？ 因为 zip 是“最短截断...

Golang指针在JSON处理中 序列化与反序列化问题

指针在Go的JSON序列化中用于精确表达字段是否存在或为null，json.Marshal会将nil指针编码为null，非nil指针解引用后输出值；反序列化时，null值使指针为nil，有值则分配内存；配合omitempty，仅nil指针被忽略，适用于PATCH更新；需注意解引用panic、零值误判和内存开销。 在Go语言中，指针与JSON的序列化和反序列化密切相关，尤其是在处理结构体字段时。使用...

Go语言中高效转换字节序列为Float32数组的指南

本教程详细阐述了在Go语言中如何将字节序列转换为float32浮点数数组。核心方法是利用encoding/binary包处理字节序（endianness）和math.Float32frombits函数进行位转换。文章涵盖了两种常见的输入场景：直接的字节字符串和十六进制字符串，并提供了清晰的代码示例和关键注意事项，确保数据转换的准确性和鲁棒性。1. 问题背景与挑战 在跨语言或跨系统通信中，例如pyt...

javascript数组如何实现斐波那契序列

在javascript中，利用数组实现斐波那契序列最有效的方法是迭代法，1. 通过初始化数组存储前两个数，2. 使用循环计算后续数值并存入数组，避免递归的重复计算和栈溢出问题，3. 数组充当记忆化工具，实现动态规划以空间换时间，4. 可自定义起始值以适应不同需求，5. 对大数场景使用bigint防止溢出，6. 数组还可扩展用于解决斐波那契类问题如爬楼梯。该方法时间复杂度为o(n)，空间复杂度为o(...

MySQL 序列使用详细说明

MySQL通过AUTO_INCREMENT属性实现序列功能,用于自动生成唯一的整数值,常用于主键或唯一标识符列,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧 目录1.创建序列（定义 AUTO_INCREMENT 列）2.使用序列（插入数据时自动生成值）3.获取当前序列值4.重置序列值5.完整示例6.注意事项在 MySQL 中，序列（Sequence）功能通常通过 AUT...

掌握 requests-mock：高效模拟动态 URL 请求与响应序列

本教程深入探讨如何使用 requests-mock 库高效模拟 Python 中 requests 库发起的 HTTP 请求，特别是针对包含动态参数（如页码）的 URL。文章将详细介绍如何利用正则表达式匹配 URL，并通过 side_effect 参数模拟一系列不同的响应，从而在测试环境中精确控制外部 API 调用的行为，确保测试的隔离性和可靠性。在开发与外部 api 交互的 python 应用时...