先说一个我自己的体会在算法面试和实际项目的文本比对里最长公共子序列Longest Common Subsequence简称 LCS是我见过出场率最高的问题之一。不管是比对两份代码的差异、做相似度去重还是给古代文献做字词对齐LCS 都是底层核心。很多朋友第一次接触它时会被“子序列”三个字绕晕以为和字符串匹配是一回事等到做动态规划状态转移时又开始纠结下标从 0 还是从 1 开始。这篇博文我会从最基础的定义一路讲到工程实现包括动态规划表格怎么填、空间怎么省、怎么把具体序列打印出来还会补充最长公共子串、编辑距离这些“亲戚算法”的对比。内容适合刚接触算法的学生也适合要在真实项目中落地的人。只要你能跟着把状态转移想明白后面所有的变体都会变得很自然。1. 从“找相同”说起LCS 到底在算什么1.1 子序列和子串一字之差差之千里先明确两个概念子串是连续的子序列不要求连续只要保持相对顺序即可。比如字符串ABCD它的子串包括ABC、BCD、ABCD而子序列还包括ACD、ABD这样跳着取的组合。“最长公共子序列”就是找两个字符串都包含的、最长的那个子序列。举个例子ABCBDAB和BDCABA的一个 LCS 是BCBA长度是 4。注意BCBA在两个字符串里都不是连续出现的但字符的相对顺序完全一致。这一点很重要LCS 比较的是“顺序上的雷同”不是“连续片段的重合”。这一点也让 LCS 非常适合做模糊匹配。比如代码重构后变量名变了、空行删了但函数调用的逻辑顺序还在LCS 能捕获这种顺序上的共性而连续子串匹配在这种场景下会直接失效。1.2 有哪些场景非得用 LCSLCS 不是一个躺在教科书里的抽象模型它在真实世界里随处可见。第一类是版本差异对比。很多代码托管平台的 diff 功能、文本对比工具核心算法就是 LCS 或其变体。两个版本的文本被拆成行行与行之间做 LCS 匹配相同行保留不同行标记为删除或新增。你看到的红绿对比本质上就是 LCS 找出的“相同骨架”。第二类是生物信息学里的序列比对。DNA 序列和蛋白质序列的对齐本质上是在找两条序列里最相似的公共部分。虽然生物信息学中常用的比对算法会更复杂比如加空格、打分矩阵但 LCS 是理解那些复杂算法的基础。第三类是信息检索和数据清洗。网页去重、新闻标题相似度判断、API 请求日志的模式抽取都可以借助 LCS 的长度或比例来判断两条记录的相似程度。两个标题如果公共子序列很长就算中间插了一些口水词也大概率是同一篇文章。适应这些场景的通用套路是先算出 LCS 长度再做归一化得到相似度如果还要高亮差异就再把具体公共序列回溯出来。你要是理解了 LCS等于把这些应用的地基一次性打通。2. 动态规划解法的完整拆解2.1 状态、转移、边界推导一遍就忘不掉LCS 的正统解法是动态规划。为什么用 DP因为两个字符串的公共子序列问题具有“最优子结构”如果你已经知道了两个前缀的 LCS再往后延长一个字符时只需要看新字符是否相等就能决定要不要把 LCS 长度加一。这天然适合用子问题的解来构造大问题的解。定义状态dp[i][j]表示字符串A[0..i-1]和B[0..j-1]的 LCS 长度。注意这里的下标偏移dp的第 0 行和第 0 列表示其中一个字符串为空的情况空串和任何串的 LCS 都是 0所以dp[0][j] 0dp[i][0] 0。转移分两种情况如果A[i-1] B[j-1]说明当前这两个字符可以拼到已有的公共子序列后面所以dp[i][j] dp[i-1][j-1] 1。如果不相等当前字符不可能同时成为新公共子序列的结尾LCS 只能从两个子问题里选较大的那个dp[i][j] max(dp[i-1][j], dp[i][j-1])。这个状态转移是理解 LCS 的关键也是面试官最爱考的点。很多初学者会把不相等的情况漏掉或者把dp[i][j]写成dp[i-1][j] dp[i][j-1]那是错的。因为公共子序列只有一条不能把两边都取只能择优。2.2 表格填法拿一个具体例子走一遍光看公式还不够直观我习惯在纸上画一张表格。假设我们要算A ABCBDAB和B BDCABA的 LCS。先把矩阵表头和初始行、初始列填好空BDCABA空0000000A0?B0C0B0D0A0B0按行从左到右填。第一行第一列A[0] AB[0] B不相等所以dp[1][1] max(dp[0][1], dp[1][0]) 0。第一行第二列A[0]A与B[1]D不等继续取 0。第一行第三列A[0]A与B[2]C不等0。第一行第四列A[0]A与B[3]A相等于是dp[1][4] dp[0][3] 1 1。第一行后面继续往右填每次都看当前字符是否相等再取上、左的最大值。整张表填完后右下角dp[7][6]就是最终结果。这里我不把整张 8x7 表格全部列出来因为手工填一遍比看表格更有用。建议你动手填到一半感受一下“不相等时取上方和左方最大值”这个规则的具体含义它其实是用两个较短前缀的答案来逐步“逼近”全局答案。填完后你会发现dp里的数值从左上方到右下方呈现出一种平缓增长的趋势每次遇到相等字符才会加 1。这种趋势可以用“长度只增不减”来理解前缀越长公共子序列不可能变短。2.3 复杂度分析时间能忍空间怎么优化二维 DP 的复杂度非常明确时间和空间都是O(m*n)m和n是两串长度。如果两个字符串都是几千的规模二维数组完全没问题但如果一边是几万、另一边是几万内存占用就可能顶到几百 MB这时候就必须做空间优化。时间复杂度的优化空间不大至少标准 LCS 没有业界公认的亚平方通用算法。所以工程上主要优化空间。最简单的办法是只保留两行dp因为每一行的值只依赖上一行和当前行的左边一个格子。这样空间从O(m*n)变成O(min(m, n))。如果你想进一步压到线性空间且还要打印完整序列那就得用到分治思路。后面我会专门讲这些操作。3. 工程级实现从单解到打印完整序列3.1 基础版 DP 代码五分钟跑通先把最直接的双重循环实现写出来。我习惯用 Python 演示因为它够直白方便大家迁移到自己熟悉的语言。def lcs_length(a: str, b: str) - int: m, n len(a), len(b) # 初始化 (m1) x (n1) 的二维表表里全是 0 dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]这段代码里最容易出错的地方是二维数组的构造。有人会写成dp [[0] * (n 1)] * (m 1)这在 Python 里会埋雷所有行其实是同一个列表对象改一行其他行也跟着变。我强烈建议用列表推导式创建每一行而不是用乘法复制行。另一个容易忽视的点是a[i - 1]的偏移。这里循环从 1 到m索引i-1正好对应字符串的第i个字符。如果你从 0 开始循环又掉过头来i直接当字符串索引边界就会乱。3.2 空间优化滚动数组把 O(m*n) 压成 O(min(m,n))如果只需要 LCS 长度二维表其实没必要全部保留。因为第i行只依赖于第i-1行而第i-1行之前的行永远不会再被用到。我们可以用两个长度为n1的一维数组来回交替甚至一个数组加一个左上方暂存变量就够。def lcs_length_optimized(a: str, b: str) - int: m, n len(a), len(b) if m n: # 让列数更小省空间 a, b b, a m, n n, m prev [0] * (n 1) curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: curr[j] prev[j - 1] 1 else: curr[j] max(prev[j], curr[j - 1]) # 当前行变成下一轮的上一行 prev, curr curr, prev # 清空 curr避免旧值残留 curr [0] * (n 1) return prev[n]这里的prev[j]是上一行当前位置curr[j - 1]是当前行左侧正好对应二维转移方程需要的两个值。为了让空间更小我通常在开始前比较两串长度把短的放在B的位置让数组宽度取较小值。这种“宽窄交换”在很多字符串 DP 题里都能应用是一招通用技巧。如果你还想更极端一点可以只用一个数组并用一个变量diag保存左上角的值。不过那个写法比较复杂除非你在一个内存受限的嵌入式环境里否则用prev/curr双数组完全够用可读性也更好。3.3 回溯打印 LCS记录决策路径长度知道了很多时候你还要知道公共子序列具体是什么。打印 LCS 的常规做法是在填dp表的同时开一个等大的direction数组或者直接在dp表上记录三个方向的来源左上、上、左。def lcs_print(a: str, b: str) - str: m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] # 0: 左上, 1: 上, 2: 左 direction [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 direction[i][j] 0 elif dp[i - 1][j] dp[i][j - 1]: dp[i][j] dp[i - 1][j] direction[i][j] 1 else: dp[i][j] dp[i][j - 1] direction[i][j] 2 # 回溯 i, j m, n res [] while i 0 and j 0: if direction[i][j] 0: res.append(a[i - 1]) i - 1 j - 1 elif direction[i][j] 1: i - 1 else: j - 1 return .join(reversed(res))这里有一个细节在elif dp[i - 1][j] dp[i][j - 1]中我使用了。当两个方向长度一样时往上走和往左走都行但选择的偏好会影响最终打印出的序列内容。如果存在多个 LCS不同偏好打印出来的结果可能不同。所以你在做 diff 工具时要特意想清楚希望保留哪一个。一般选择“向上优先”会让回溯更偏向于匹配A串里的字符而“向左优先”则偏向于匹配B串里的字符。调试回溯逻辑时我强烈建议你写一个测试函数自己构造一个短例子然后手动验证打印结果是不是两个字符串的公共子序列并且长度等于dp[m][n]。这一步能拦住 90% 的隐藏 bug。3.4 再进一步Hirschberg 线性空间打印direction数组本质上是把整个 DP 表的方向记录了下来空间仍然是O(m*n)。如果两个字符串都是几万甚至几十万字符比如处理版本历史文本空间会爆炸。这时候要用 Hirschberg 算法。Hirschberg 的核心思路是分治把A从中点切成A1 A[:mid]和A2 A[mid:]然后找到某个j把B切成B[:j]和B[j:]使得LCS(A, B) LCS(A1, B[:j]) LCS(A2, B[j:])。这个j可以通过分别计算前缀 LCS 和后缀 LCS 来确定最后递归构造序列。步骤大致是对A1和B做一遍正向 DP得到每个j对应的前缀 LCS 长度数组L[j]。对A2和B做一遍反向 DP得到后缀 LCS 长度数组R[j]。对每个j计算L[j] R[j]找到最大值对应的切分点。递归地在A1, B[:j]和A2, B[j:]里分别打印 LCS拼接起来。这个算法的空间是O(n)时间是O(m*n)。因为每一层递归仍然要扫描一遍整张表但递归深度是O(log m)所以总时间还是平方级只是常数稍微大一点。对于无法承受平方级内存、但能承受平方级时间的场景比如处理超长文本但内存有限这个算法是首选。Hirschberg 实现起来比滚动数组复杂但核心还是那几个转移公式。建议先用小例子把递归切分逻辑验证清楚再上大数据否则一上来写好几百行debug 会非常痛苦。4. 实战中的变体与场景迁移4.1 最长公共子串与 LCS 的区别最长公共子串Longest Common Substring和 LCS 只有一字之差但转移方程完全不同。子串要求连续所以当A[i-1] ! B[j-1]时当前公共部分直接断掉dp[i][j]要回到 0而当相等时dp[i][j] dp[i-1][j-1] 1。最终答案是整张表里的最大值而不再是右下角。def longest_common_substring(a: str, b: str) - int: m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] ans 0 for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 ans max(ans, dp[i][j]) # 不相等时就保持默认值 0 return ans这个对比很直观LCS 看重“跳跃的骨架”子串看重“连片的内容”。做代码 diff 时通常用 LCS 思想因为一个公共函数体里混入了几行无关代码后仍然是同一个逻辑而做抄袭检测或连续重复片段发现时公共子串更有价值。4.2 相似度计算与编辑距离用 LCS 长度可以定义一个简单相似度2 * LCS_length / (len(a) len(b))。当两个字符串完全相同时这个值是 1完全不同时接近 0。这个指标在英文文献里叫 LCS-based similarity使用门槛低效果也还行。和 LCS 关系最近的一个指标是编辑距离Levenshtein Distance它表示把一个字符串变成另一个字符串所需的最少编辑操作数插入、删除、替换。编辑距离的 DP 转移很眼熟A[i-1] B[j-1]dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])编辑距离和 LCS 之间有一条常见换算关系如果只允许插入和删除不允许替换那么编辑距离等于m n - 2 * LCS_length。因为 LCS 是保留字符两侧多余字符都要删掉或插入。理解了这条关系你就能在实现“文本差异百分比”时灵活选择指标。我在实际项目里通常的做法是如果文本是自然语言用编辑距离或带权重的相似度如果是代码、配置文件这类结构化文本先按行拆分再用 LCS 判断段落层面的重合度。两者搭配起来比单一指标靠谱得多。4.3 简化版本只在乎长度时如何压缩有些场景你只想知道两个字符串有没有达到某个相似度阈值不需要拿到具体公共子序列。这时除了滚动数组还可以做小规模剪枝如果m和n中有一个为 0直接返回 0如果两串完全相同直接返回长度如果m远大于n且你只看相似度比例可以考虑只取长串的滑动窗口片段与短串比较减少计算量。还有一个小技巧当m和n差值巨大比如一个是 100 万另一个是 5那 LCS 长度最多是 5。这时你可以直接遍历短串每个字符是否按顺序出现在长串里线性复杂度搞定。这本质上是 LCS 的贪心上下界判断虽然没有全局最优但能应对很多业务上“检测是否包含大致顺序”的需求。对于严格追求效率的场景可以改用基于位运算的并行 DP。在字符集较小、串长不超过机器字长例如 64时可以用整数位掩码在O(n * ceil(m / word_size))时间内计算出 LCS 长度。这类实现比较偏门但当你做大规模基因序列比对时性能差距立竿见影。5. 常见问题与排查笔记5.1 边界条件出错index 从 0 还是 1 开始这是 LCS 实现里出现频率最高的 bug。很多人一上来就写for i in range(len(a))然后在比较时用dp[i][j]这样做不是不行但状态定义和字符串索引都要跟着改稍不留神就越界。我的建议是永远保持“dp[i][j]对应前i个字符和前j个字符”这个定义循环从 1 开始比较时用a[i-1] b[j-1]。这样边界条件统一为第 0 行、第 0 列全是 0语义清晰不容易错。如果你看到某个实现从 0 开始也能跑那大概率它的dp定义里dp[i][j]对应的是从当前位置起的后缀思路不同但也能正确只是混用两种定义最容易翻车。5.2 多个 LCS 时回溯打哪一个LCS 不唯一。比如A ABCB ACB公共子序列可以是AB也可以是AC。回溯算法在出现“上左”相等时会偏向某一方向这决定了你打印的是哪个。如果你需要枚举所有 LCS事情会复杂很多需要沿着所有可走的方向做 DFS并去重。复杂度可能指数级因为 LCS 数量本身可能指数级。业务上极少需要全枚举但如果你要做“所有可能对齐方案”的分析建议限制输出数量或者用带剪枝的搜索。另一个常见坑是打印时忘记把收集到的字符反转。回溯是从末尾倒着走的收集顺序是反的直接拼接会是BCB而不是BCBA。这个问题在面试现场非常常见画图推演比硬记代码要可靠得多。5.3 字符串太长内存爆炸空间优化的实际经验我曾经处理一对超过 5 万行的源码版本用基础二维 DP 直接创建了 5 万乘 5 万的数组。每个元素用 4 字节整数存需要差不多 10 GB 内存程序瞬间就崩溃了。后来改成滚动数组内存降到几百 KB只要计算长度就没有任何压力但若要打印具体 diff还需要 Hirschberg 方案否则只能退回用direction表同样会爆炸。如果你不是做算法研究只是要在业务代码里比对两个大文件还有一个更工程化的招按块切分。先把文本按段落、函数或空行切块每个块内部用 LCS再把块级结果拼接起来。这样虽然得不到全局最优解但速度极快内存也稳。很多真实 diff 工具并没有追求全局最优而是做了启发式切分就是这个原因。5.4 设计测试断言防止自己骗自己一个健壮的 LCS 实现必须有系统性测试否则非常容易“表面正确实际错误”。我自己的测试清单包含下面几类两个空串lcs_length(, ) 0一个空串一个非空串 0完全相同lcs_length(abc, abc) 3完全不同的字符集lcs_length(abc, xyz) 0逆序串lcs_length(abc, cba) 1因为任何公共子序列只有单个字符有重复字符的复杂串lcs_length(ABCBDAB, BDCABA) 4打印函数还要额外验证输出结果的每个字符同时按顺序出现在两个原始字符串中且输出长度等于 DP 长度。这个断言可以直接写进单元测试运行一次就知道回溯逻辑对不对。最后的个人建议我在实际开发里最常用的并不是完整的回溯打印而是先快速算长度再用长度做相似度阈值过滤最后才对少量候选做完整回溯。这样能避免大部分无谓计算。如果你刚开始学 LCS不要只盯着代码一定亲手在纸上填一张表体会“不相等时取上左较大值”这句话的几何意义。一旦填过两三张表再看任何变体算法都会觉得顺理成章。顺带分享一个小技巧做文本行级 diff 时可以把每一行哈希成一个整数这样 LCS 比较的就是整数序列速度比逐行字符串比较快一个数量级。哈希碰撞的概率虽然存在但在常规业务场景里用 64 位哈希足够安全。如果你要绝对准确再在哈希相等的位置二次校验原始文本即可。这个小技巧我屡试不爽推荐给所有需要在项目里手写 diff 的朋友。