最长公共子序列（LCS）算法教程 📚

什么是 LCS？

最长公共子序列（Longest Common Subsequence，简称 LCS）是字符串匹配中的经典算法，常用于比较两个序列的相似性。它不强调字符连续性，而是寻找最长的递增顺序匹配子序列。例如，对于字符串 ABCBDAB 和 BDCAB，LCS 是 BCAB（长度为4）。

核心步骤

1. 动态规划表构建
   创建一个二维数组 dp[i][j]，表示前 i 个字符和前 j 个字符的LCS长度。
2. 递归公式
   • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
   • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 填表与回溯
   从左上角到右下角填充表格，最后通过回溯找到具体子序列。

示例演示

以字符串 s1 = "ABCBDAB" 和 s2 = "BDCAB" 为例：

应用场景

• 生物信息学：比对DNA序列的相似性
• 文本编辑：计算文件差异（如Git diff）
• 字符串匹配：寻找两个字符串的共同模式
• 机器学习基础：作为动态规划算法的经典案例

扩展学习

想深入了解动态规划在算法中的应用？
👉 点击这里查看动态规划教程

小贴士

💡 LCS 与 最长公共子串（Longest Common Substring）不同，后者要求字符连续。两者都是字符串处理的基石，建议对比学习！