最长公共子串：从暴力枚举到动态规划与工程实践

最长公共子串这题我在给学员讲动态规划的时候几乎每次都会遇到。很多人拿到题就想着套“最长公共子序列”的模板结果连续性的条件一加就直接翻车。今天把这题从暴力思路到动态规划再到进阶优化完整拆一遍同时把实际工程里怎么用也给出来。不管是准备面试、搞竞赛还是工作中要做文本相似度分析这篇都应该能帮到你。老规矩先说清楚子串要求字符在原串里是连续的子序列不要求连续。这两个概念差了十万八千里理解错了整道题全废。1. 题目思路拆解先搞清楚“公共子串”到底在问什么很多人第一次拿到“最长公共子串”这个题会觉得它跟“最长公共子序列”差不多不就是少了个字母吗还真不是。子串是连续的子序列可以跳着取。随便举个例子就能看出区别abcdef和acdf最长公共子序列是acdf长度4但最长公共子串最长只有1因为没有任何一个连续片段在两个串里同时出现。这就是两种题的核心分界线。搞清楚这个区分之后接下来要回答的问题是怎么高效找出来最笨的办法是把较短串的所有子串挨个枚举出来然后拿到另一个串里去查。一个长度为 n 的串有大约 n²/2 个子串每个子串检查一下是否出现在另一个串里又得花 O(m) 的时间整体复杂度 O(n²·m)。n、m 上千就卡死了。这个复杂度明显不可接受所以我们要么用动态规划把重复计算的公共前缀信息留下来要么用更高级的字符串算法直接加速匹配过程。动态规划的思路其实很自然我们并不需要同时枚举所有子串只需要关注“以某个字符结尾的匹配长度”。假设s1[0..i]和s2[0..j]当前同时考虑如果最后一个字符s1[i]和s2[j]相等那就说明在这两个位置之前一定已经有一串连续匹配的字符长度等于dp[i-1][j-1] 1。如果不相等那就说明在当前这两个位置结束的地方不可能有公共连续片段长度直接归零。这就构成了转移方程。这里有个很多初学者会犯的错误把不相等的情况直接留 0 没问题但有人会写出dp[i][j] max(dp[i-1][j], dp[i][j-1])的小转移那就彻底变成子序列了。记住最长公共子串的转移里只有一条路可选字符相等才延续不等就全部清零没有任何“历史积累”可言。1.1 连续 vs 非连续和最长公共子序列的本质差异我拿一个话单匹配的场景再帮大家加深印象。假设你有两段指令序列想知道两段话的“共同片段”你是要找到连续相同的一句话片段还是允许中间隔几个无关词前者是公共子串后者是子序列。这两个需求在现场处理时是完全不同量级的逻辑子串问题可以用滚动窗口直接卡子序列问题就必须维护状态表。从代码上说最长公共子序列的转移是dp[i][j] max(dp[i-1][j], dp[i][j-1])字符相等时还可以从dp[i-1][j-1] 1转移过来。而最长公共子串只有一个转移来源dp[i][j] (s1[i-1] s2[j-1]) ? dp[i-1][j-1] 1 : 0。正是因为只有一个来源最终答案不是dp[n][m]而是整个 dp 表里的最大值。这点变化直接决定了后续所有代码写法。很多人刷题时候会有个疑问既然最长公共子序列能直接输出dp[n][m]为什么最长公共子串不能因为子序列的全局最优解天然落在最后一个状态里它是累加转移的结果而子串的匹配是随时可能中断的某段公共子串可能在表格中间就已经结束了后面全部被清零。所以答案必须边转移边记录。1.2 从暴力枚举到动态规划重复计算是怎么被消除的我们再来看看动态规划到底“优化”了什么。暴力做法里同一个子串abc会先被当成a的子串去查再当成ab的子串去查最后才是abc重复计算特别严重。动态规划的核心贡献是把“以某个位置结尾的、两个串能共同匹配到的最大长度”这张表记录下来每个字符对只计算一次后续直接查表。我习惯把这张表画出来感受一下。比如s1 abcdes2 bcd画一个 6×4 的表多一行一列处理边界你会看到(2,2)位置匹配了b(3,3)位置匹配了c(4,4)位置匹配了d连续形成长度3的斜线。最大公共子串其实就是表格里最长的“连续对角线”。动态规划不过是用代码把“对角线延续”的过程标准化了。这也是为什么我建议初学者第一次学这题时一定要把 dp 表手动推一遍。推完你就明白所谓的dp[i][j] dp[i-1][j-1] 1就是在对角线上往前走一步任何断点都会重置。这个直觉建立之后空间优化也顺理成章——你只需要保留上一行的数据因为当前状态只依赖左上角。1.3 关键状态定义为什么dp[i][j]必须表示“以当前字符结尾”的长度定义状态时“以当前字符结尾”这六个字是命门。如果定义成“前 i 个字符和前 j 个字符之间的最长公共子串长度”那这个状态就和子序列混为一谈了因为“之间”不存在连续性限制。必须定义成dp[i][j]表示s1的前 i 个字符中以第 i 个字符结尾的连续片段能和s2前 j 个字符中以第 j 个字符结尾的连续片段匹配的最大长度。这个定义的好处是让“连续性”被天然编码进状态里。每个格子只记录最后一段匹配了多长前面断没断过完全不用关心。只要当前两个字符相等就在左上角基础上加1一旦不相等当前格子直接归零因为“以当前字符结尾的连续匹配”根本不存在。这种定义方式非常干净也方便回溯因为end_pos - max_len到end_pos这一段就直接是答案。我在工程里做日志相似分析时也一直用这个定义。两段日志切分成字符数组之后用相同的方式算公共连续子串定位出来的就是真正重复的那一段而不是跨行的相似片段。连续性在这里不仅是对的概念更是工程上“片段可定位”的前提。2. 经典动态规划实现与边界细节理解了状态之后写代码就快了。先给一个最标准的二维 DP 版本这段代码我建议所有人都能默写def longest_common_substring(s1: str, s2: str) - str: n, m len(s1), len(s2) # 多开一行一列用 0 做边界避免单独处理 i0 或 j0 dp [[0] * (m 1) for _ in range(n 1)] max_len 0 end_pos 0 # 记录最长公共子串在 s1 中结束的下标 for i in range(1, n 1): for j in range(1, m 1): if s1[i - 1] s2[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 if dp[i][j] max_len: max_len dp[i][j] end_pos i else: dp[i][j] 0 return s1[end_pos - max_len:end_pos]代码非常短但里面有几个细节我要重点强调。第一dp表的维度是(n1) x (m1)行和列都多开了一个位置这样第一行和第一列天然为 0处理边界的时候不用写一堆if。第二循环里的下标i-1和j-1是在访问字符串的真实字符千万别手滑写成s1[i]否则会越界。第三每次更新dp[i][j]之后要立刻和max_len比较并顺手记录end_pos i最后通过下标切片直接得到完整答案。如果你只需要最长长度不需要输出具体子串那么end_pos可以不记录直接返回max_len即可。但面试中十有八九会追问“怎么输出子串”所以建议从一开始就养成本记录end_pos的习惯省得到时候临时改。2.1 为什么多开一行一列能让代码更简洁有读者可能好奇边界到底卡在哪里看这段逻辑当i 1且j 1时要访问dp[0][0]。如果 dp 表只开了n x m那么大的dp[0][0]虽然存在但它并不是我们想要的“上一行上一列”的语义值。多开一行一列之后dp[0][j]和dp[i][0]天然代表“空串参与匹配”的结果一定是 0。这样第一轮循环里dp[1][1] dp[0][0] 1 1所有边界条件都被统一处理掉了逻辑非常干净。这种“哨兵行/哨兵列”的技巧在动态规划里极其常见处理编辑距离、最大正方形、最小路径和等问题时都可以这么干。省去大量if i 0 or j 0的分支判断代码减法比逻辑加法更容易维护。2.2 不相等时必须清零一个经典的翻车点我再单独强调一次这个清零操作。很多从“最长公共子序列”转过来的同学写到这里会顺手写成dp[i][j] max(dp[i-1][j], dp[i][j-1])然后还觉得自己是对的。这个写法在子序列里没问题但在子串里就完全错了。原因是一旦s1[i-1] ! s2[j-1]以这两个字符结尾的公共连续片段长度就是 0不可能从左边或者上边“继承”任何长度。如果你把历史最大值继承过来等于允许了中间断开那就变成了子序列问题。我用一个例子让大家看明白s1 abcs2 ac。按错误的继承写法dp最后会得到 2因为有a和c但真正的最长公共子串只有 1因为a和c在abc里不连续。所以这个else: dp[i][j] 0不是可有可无是整个“连续性”约束的代码化身删了它就是原则性错误。2.3 答案为什么不一定在表格右下角还有一个高频疑问为什么最后不能直接输出dp[n][m]原因很简单最长公共子串可能出现在两个串任意一段匹配成功的位置。比如s1 xyzabcs2 abcxyz最长公共子串abc出现在s1的第 4~6 位、s2的第 1~3 位而dp[6][6]对应的是z和y不相等值为 0。右下角是什么都不代表。所以标准做法是维护一个全局max_len每更新一格就与它比较一次。这也意味着整个 dp 表里可能有多个位置同时达到最大长度。如果你需要返回最早出现的那一个记录end_pos时用而不是如果返回最长的任意一个用就够了。实际面试里通常只要求任意一个所以我在代码里用了。3. 空间优化从 O(n*m) 到 O(min(n,m)) 的一维滚动数组二维 dp 的优点是直观、好理解缺点是占空间。如果两个字符串长度都是 5000二维表就要开 2500 万个格子Python 里光这一个列表就够喝一壶。好在这题的状态转移只依赖左上角dp[i-1][j-1]也就是说当前行更新时只需要上一行的数据所有更早的行都可以丢掉。滚动数组应运而生空间复杂度直接降到 O(m)。这个优化在工程里的意义非常实际。你处理的不一定是单次请求可能是循环跑几千对文本片段。每一对都开一个二维表内存释放不及时进程直接爆掉。滚动数组能让你在一大段文本集合上稳定跑完而不至于让 GC 频繁喘息。3.1 滚动数组的思路只保留上一行我们用一个一维数组dp在进入第 i 轮循环前dp[j]里存的是上一行、也就是dp[i-1][j]的值。进入第 i 轮后我们从头到尾更新dp[j]让它变成当前行的值dp[i][j]。因为计算dp[i][j]只用到dp[i-1][j-1]也就是“上一行的左上角”所以只要我们在覆盖之前把左上角旧值先保存下来就可以一行一行地滚动。问题来了dp[j-1]在更新之后已经是当前行的新值不再是上一行的旧值了所以不能用dp[j-1]来充当左上角。正确做法是设置一个pre变量在每轮覆盖前先把dp[j]的旧值存到临时变量里然后用pre做转移最后把临时变量赋给pre作为下一轮需要的左上角。def longest_common_substring_optimized(s1: str, s2: str) - int: n, m len(s1), len(s2) # 空间优化只保留一行 dp [0] * (m 1) max_len 0 for i in range(1, n 1): pre 0 # pre 表示 dp[i-1][j-1] for j in range(1, m 1): temp dp[j] # 保存 dp[i-1][j]下一轮要当作左上角用 if s1[i - 1] s2[j - 1]: dp[j] pre 1 if dp[j] max_len: max_len dp[j] else: dp[j] 0 pre temp # 当前 dp[j] 的旧值成为下一轮的左上角 return max_len这里pre初始化为 0对应每行最左侧的哨兵列。内层循环中先拿temp保存dp[j]更新前的旧值更新完dp[j]后把temp赋给pre。这样到了 j1 位置pre就是dp[i-1][j]恰好是新位置的左上角。这个手法是滚动数组里最容易出错的地方写的时候脑子一定要清醒。3.2 如果只求长度输出子串要怎么改造空间优化版本里我没记录end_pos因为滚动数组一覆盖旧的位置信息就丢了。如果要同时输出子串也可以做。两种方案供选择第一种最省事的办法先用滚动数组算出max_len如果它是 0 直接返回空串。否则再回到二维 DP 重新算一遍最大值的位置因为有了max_len之后只需要找到第一个满足dp[i][j] max_len的位置即可输出答案。代价是时间翻了 1.5 倍左右但代码改动极小。第二种维护额外变量在滚动数组更新过程中记录当前达到max_len时的i和j就行。因为 s1 的下标i在每轮外层循环里是固定的只要在内层循环中能知道 s2 的j就可以定位子串。具体来说当dp[j]更新后大于max_len时记录end_pos is1 中的结束位置和j_opt j。最后只要s1[end_pos - max_len: end_pos]就能取出答案这个字符串的结束位置在 s2 里对应的下标就是end2 j_opt需要时也可以从 s2 切出来验证。如果想进一步压空间还有一个常用的技巧比较n和m的大小把短串放在外层循环长串放在内层让滚动数组的长度等于较长串的长度不对实际应该让滚动数组等于较短串的长度不过这会有个问题外层循环走了短串长度内层是长串转移时下标对调了需要保证 dp 里存的是短串那一维。为了控制代码复杂度很多人干脆固定用 s2 的长度作为滚动数组长度实测下来差别不大因为两个串通常在同一量级。3.3 空间优化后的复杂度分析优化后时间仍然 O(nm)但空间变成 O(min(n,m))若用短串作为外层循环则更省。有一种说法是可以用字符串哈希 二分做到 O((nm) log L)这个不是 DP 范畴留到第 4 节说。但要注意滚动数组的 O(nm) 时间在 n、m 达到 1e5 时依然不可用这时候必须上更进阶的算法不是靠省空间能解决的。我实测过一串典型数据n m 10000二维 DP 在 Python 里要跑 1 亿次状态转移耗时在 8 秒以上滚动数组省内存但不省时间只是把内存占用从接近 800MB 降到 80KB 左右。所以在数据规模大的场景下首先明确时间瓶颈再决定要不要换算法。4. 进阶思路数据规模变大时的杀手锏动态规划是 O(nm)当 n、m 都到 1e5 量级的时候二维 DP 连时间都撑不住。工程里真遇到长文本比对比如比对两段 10 万字符的日志序列nm 就是 100 亿次操作任何语言都很难在合理时间内跑完。这时候需要换思路。4.1 二分 字符串哈希把问题化为“判定存在性”核心思路其实不难如果存在长度为 L 的公共子串那么长度比 L 小的公共子串也一定存在。这个单调性让“最长长度”问题可以二分。具体做法是枚举一个候选长度 mid把 s1 中所有长度为 mid 的子串哈希值扔进一个集合然后枚举 s2 中所有长度为 mid 的子串看哈希值是否在集合中。存在则说明当前长度可行把low往上提不存在则把high往下压。整体复杂度 O((nm) log L)瓶颈在每一轮都要生成所有子串的哈希。生成子串哈希时最常用的是滚动哈希也叫 Rabin-Karp 风格的前缀哈希。实例如下def check(mid: int) - bool: seen set() # 计算 s1 中所有长度为 mid 的子串哈希 h 0 base 131 p pow(base, mid, MOD) for i in range(len(s1)): h (h * base ord(s1[i])) % MOD if i mid: h (h - ord(s1[i - mid]) * p) % MOD if i mid - 1: seen.add(h) # 在 s2 中找相同哈希 h 0 for i in range(len(s2)): h (h * base ord(s2[i])) % MOD if i mid: h (h - ord(s2[i - mid]) * p) % MOD if i mid - 1 and h in seen: return True return False这个写法有个隐患哈希碰撞。单哈希遇到构造数据可能出错严谨的工程实现建议用双哈希或者 64 位整数配合随机种子。我一般偷懒做法是用两个不同的模数分别计算两个哈希值同时相等才判定子串相同实测下来很稳。另外注意哈希方法只能高效判断“是否存在长度至少为 mid 的公共子串”如果想知道最长到底多长二分长度后如果 mid 可行继续往上找即可。但补出一个具体子串还要再做一次 O(nm) 的扫描在可行时记录位置。这个序列化步骤容易忽略严格来说代码量不大但很影响体验。4.2 后缀自动机线性时间解决最长公共子串如果追求理论最优复杂度后缀自动机SAM是终点。对 s1 构建 SAM然后用 s2 在上面匹配维护当前匹配长度cur_len当字符能沿转移边走时cur_len不能走时沿着后缀链接跳回直到找到能走的位置或者回到根。匹配过程中cur_len的最大值就是答案。SAM 的构建代码比较长这里给匹配的核心思路class SAMNode: def __init__(self, length0, link-1): self.length length self.link link self.next {} def build_sam(s: str) - list[SAMNode]: st [SAMNode(0, -1)] last 0 for ch in s: # 创建新节点按标准SAM流程扩展 cur len(st) st.append(SAMNode(st[last].length 1, -1)) p last while p ! -1 and ch not in st[p].next: st[p].next[ch] cur p st[p].link if p -1: st[cur].link 0 else: q st[p].next[ch] if st[p].length 1 st[q].length: st[cur].link q else: clone len(st) st.append(SAMNode(st[p].length 1, st[q].link, dict(st[q].next))) while p ! -1 and st[p].next.get(ch) q: st[p].next[ch] clone p st[p].link st[cur].link st[q].link clone last cur return st def longest_common_sam(s1: str, s2: str) - int: sam build_sam(s1) v, cur_len, max_len 0, 0, 0 for ch in s2: while v ! -1 and ch not in sam[v].next: v sam[v].link if v ! -1: cur_len sam[v].length if v -1: v 0 cur_len 0 else: v sam[v].next[ch] cur_len 1 if cur_len max_len: max_len cur_len return max_lenSAM 的说明往往被写得很难懂我建议先放弃细究内部原理把它当成一个“对字符串建立自动机自动机支持快速匹配任意文本”的黑盒。在实际比赛中SAM 的构建代码长、调错困难所以如果只是参加一般算法竞赛二分哈希往往是性价比更高的选择。4.3 算法选型的决策参考遇到这种题先别急着开写看一眼数据范围再决定用哪个方案。我整理了一张选型表直接照着选就行数据规模推荐方案复杂度备注n, m ≤ 1000二维 DPO(n*m)代码最短最稳n, m ≤ 10000一维滚动 DPO(n*m)内存友好时间能接受n, m ≤ 1e5二分 哈希O((nm) log L)需要双哈希防碰撞n, m ≥ 1e5追求极限后缀自动机O(nm)代码复杂适合竞赛硬核向别小看这张表。我见过太多人拿着哈希方法去做小规模数据代码写得又臭又长最后还没 DP 快。反过来也有人拿着 DP 去跑 10 万级数据跑半天出不来结果。数据范围决定算法这是解题的第一直觉。5. 实际应用场景这题不只是在竞赛里刷分最长公共子串听起来很理论但它实实在在出现在很多工程任务里。我把平时做过的几个典型场景列出来方便大家理解这题的实用价值。5.1 文本查重与相似度定位论文查重、代码查重、商品描述查重的核心环节往往都需要抽取“连续相同片段”。拿两段文本对比找到最长的连续相同片段长度再除以总长度就能得到一个基础的相似度分数。这个指标比单纯统计词频要可靠得多因为它抓住了“逐字搬用”的特征。代码查重时更有意思。把代码去掉所有空白和注释之后按字符数组处理然后跑一遍最长公共子串能精确定位哪些行的内容是重复拷贝过去的。很多查重系统会进一步把超过阈值长度的公共子串全部标记出来而不只是最长的那一段。这个场景下二维 DP 的 dp 表其实很有用因为表里出现的每一个高值点都是一段相似片段的候选。5.2 生物信息学中的序列比对DNA 和蛋白质序列的比较是字符串算法的经典应用场景。生物学上两条序列之间共享一段较长的连续相同片段往往意味着这段序列在进化上高度保守可能对应某个重要的功能区域。算法上这就是典型的最长公共子串问题。真实基因序列动辄几百万字符直接跑 O(n*m) 是不现实的所以工业界会使用后缀数组、FM-index 等更激进的数据结构。但比赛和面试的简化版用最长公共子串来理解序列共性是没问题的。你甚至可以写一个小脚本把两条 DNA 片段输入进去快速找到它们共有的最长保守片段再拿去数据库比对。5.3 日志异常定位与相似请求聚合在后端开发中大量日志来自同一套代码框架不同请求的日志结构相似、细节不同。为了把日志聚合成几个典型“模式”我经常用公共子串计算两条日志的公共部分。如果公共子串长度占了较短日志的 80% 以上基本可以判定这两条日志属于同一种模式可以归并处理。更进一步当线上出现大规模重复异常日志时不同节点、不同时间的报错里往往共享同一段异常堆栈。抓出最长公共子串就能快速判断“所有节点是不是挂在同一个调用链上”。这个场景下不一定需要字母级别精确有时把日志按行切分每一行当成一个“字符”再做最长公共子串效果反而更好。6. 常见问题与排查技巧实录写这题的人多踩坑的人更多。我把这些年见过的典型错误整理成一个速查表方便大家定位问题。6.1 高频翻车现场速查表现象可能原因解决方案返回结果是空串没正确初始化end_pos或字符串本身无公共子串检查字符串是否为空以及max_len初始是否为 0结果长度偏大不相等分支用了继承式转移确认不相等时dp[i][j] 0输出答案和预期不一致下标偏移写错用了s1[i]检查循环里是否用s1[i-1]内存超限n、m 太大还开二维数组改用滚动数组或哈希二分结果对但时间超时数据规模大还用了 O(n*m)根据数据规模换算法处理大小写时答案异常未统一字符预处理比对前统一转成小写或大写多个相同长度答案时输出不稳定和的选择问题按需求决定输出最早或最长的答案6.2 对拍测试用一个暴力解法做基准我每次写完这类算法一定会做对拍测试不过程序的核心逻辑没问题。所谓对拍就是写一个极其简单但一定正确的暴力版本再用随机数据把优化版本和暴力版本的结果进行比较。暴力版本思路很简单枚举 s1 的所有开始位置 i再枚举所有结束位置 j判断s1[i:j]是否出现在 s2 里记录最长那一个。这个版本正确性一目了然虽然慢但因为只是测试数据量级可以控制。然后随机生成几百组小写字母、数字混合字符串长度从 1 到 50 不等跑一轮对比。只要有一组结果不同立刻把两个串和两个版本的差距打印出来基本就能定位到是状态转移还是回溯逻辑出了问题。这个习惯帮我节省了大量时间。尤其滚动数组版本刚写完时pre和temp的顺序搞反是常事肉眼很难发现但一拍就出来了。6.3 我自己的调试心得最后一个建议也是我个人的习惯调试动态规划问题时小数据上打印 dp 表是最快的方式。拿s1 abcde、s2 bcd这种小样例把 dp 表一行行打出来你会看见一条清晰的对角线。这一步做完整个转移过程就刻在脑子里了之后写任何变体都不容易出错。如果打印出来的表里对角线断了或者多出了不该有的数字那就顺着值最大的格子往回查看它的左上角是不是正确的连续值。这种“肉眼验证状态表”的方法比单纯读代码有效得多。另外建议大家养成一个习惯把这题和“最长公共子序列”“编辑距离”放在一起对比复习。它们共享同一套 dp 表的思考框架但每个都有自己独特的转移约束。对比着学记忆会深很多面试时被问到变体题也更容易变通。三分治七分练最长公共子串这种基础题写到条件反射才算真掌握。