最长公共子序列是什么？LCS的求解方法-js教程-PHP中文网

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

幻夢星雲

发布： 2025-08-22 14:53:01

原创

690人浏览过

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

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

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

解决方案

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

具体来说，我们可以构建一个二维数组

dp

登录后复制

，其中

dp[i][j]

登录后复制

表示字符串

text1

登录后复制

的前

登录后复制

个字符和

text2

登录后复制

的前

登录后复制

个字符的最长公共子序列的长度。

初始化：

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]

登录后复制

对应的是前

登录后复制

个字符）：

如果
```
text1[i-1]
```
登录后复制
等于
```
text2[j-1]
```
登录后复制
：这意味着当前字符匹配了，那么LCS的长度就可以在前一个匹配的基础上加1。
```
dp[i][j] = 1 + dp[i-1][j-1]
```
登录后复制
如果
```
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]

登录后复制

（其中

登录后复制

是

text1

登录后复制

的长度，

登录后复制

是

text2

登录后复制

的长度）就是两个字符串的最长公共子序列的长度。

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

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

换个角度看，LCS问题还具备“最优子结构”——也就是说，一个问题的最优解可以通过其子问题的最优解来构建。比如，如果你知道

text1

登录后复制

的前

i-1

登录后复制

个字符和

text2

登录后复制

的前

j-1

登录后复制

个字符的LCS，那么结合当前字符的匹配情况，就能直接推导出

text1

登录后复制

的前

登录后复制

个字符和

text2

登录后复制

的前

登录后复制

个字符的LCS。动态规划正是利用了这两大特性，通过填表的方式，自底向上地解决问题，避免了指数级的计算量，将时间复杂度优化到了 O(mn)，这对于处理较长的字符串来说是至关重要的。相比之下，暴力枚举所有可能的子序列，那简直是天文数字般的计算量，根本不现实。

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

LCS虽然听起来有点像个纯粹的算法问题，但它在实际生活和技术领域里，其实扮演着不少关键角色。最直观的，可能就是版本控制系统里的“diff”工具了。当你修改了一段代码，然后想看看和之前的版本有什么不同时，

diff

登录后复制

工具就能帮你高亮显示新增、删除或修改的部分。这里面，LCS就在幕后默默工作，它会找出两个文件（或字符串）的最长公共部分，然后那些不属于LCS的，就是被修改或新增的了。这对于代码合并、文件同步都非常有用。

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

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

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

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

知道了LCS的长度，很多时候我们还想知道具体是哪个序列。这就像你知道了考试得了多少分，但更想知道哪些题目做对了。回溯LCS的具体序列，其实就是沿着我们之前构建的

dp

登录后复制

表，从右下角

dp[m][n]

登录后复制

开始，反向推导回去。

它的逻辑是这样的：

从
```
dp[m][n]
```
登录后复制
开始，初始化一个空字符串或列表来存储LCS。
如果
text1[i-1]
登录后复制
等于
text2[j-1]
登录后复制
：这说明
```
text1[i-1]
```
登录后复制
（或
```
text2[j-1]
```
登录后复制
）是LCS的一部分。我们将这个字符添加到LCS结果中（通常是添加到最前面，因为我们是反向回溯），然后将
```
i
```
登录后复制
和
```
j
```
登录后复制
都减1，移动到
```
dp[i-1][j-1]
```
登录后复制
，继续向上左方向回溯。
如果
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，这里就需要分叉处理了。但通常我们只找一个。