企业官网建设流程全解析

最长公共子串这题，我在给学员讲动态规划的时候几乎每次都会遇到。很多人拿到题就想着套“最长公共子序列”的模板，结果连续性的条件一加就直接翻车。今天把这题从暴力思路到动态规划再到进阶优化完整拆一遍，同时把实际工程里怎么用也给出来。不管是准备面试、搞竞赛，还是工作中要做文本相似度分析，这篇都应该能帮到你。

老规矩，先说清楚：子串要求字符在原串里是连续的，子序列不要求连续。这两个概念差了十万八千里，理解错了整道题全废。

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 = "abcde"，s2 = "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 做边界，避免单独处理 i=0 或 j=0 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表的维度是(n+1) x (m+1)，行和列都多开了一个位置，这样第一行和第一列天然为 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 = "abc"，s2 = "ac"。按错误的继承写法，dp最后会得到 2（因为有a和c），但真正的最长公共子串只有 1，因为a和c在"abc"里不连续。

所以这个else: dp[i][j] = 0不是可有可无，是整个“连续性”约束的代码化身，删了它就是原则性错误。

2.3 答案为什么不一定在表格右下角

还有一个高频疑问：为什么最后不能直接输出dp[n][m]？原因很简单，最长公共子串可能出现在两个串任意一段匹配成功的位置。比如s1 = "xyzabc"，s2 = "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。这样到了 j+1 位置，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 = i（s1 中的结束位置）和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((n+m) 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((n+m) 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(n+m) 的扫描，在可行时记录位置。这个序列化步骤容易忽略，严格来说代码量不大，但很影响体验。

4.2 后缀自动机：线性时间解决最长公共子串

如果追求理论最优复杂度，后缀自动机（SAM）是终点。对 s1 构建 SAM，然后用 s2 在上面匹配，维护当前匹配长度cur_len，当字符能沿转移边走时cur_len++；不能走时沿着后缀链接跳回，直到找到能走的位置或者回到根。匹配过程中cur_len的最大值就是答案。

SAM 的构建代码比较长，这里给匹配的核心思路：

class SAMNode: def __init__(self, length=0, 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_len

SAM 的说明往往被写得很难懂，我建议先放弃细究内部原理，把它当成一个“对字符串建立自动机，自动机支持快速匹配任意文本”的黑盒。在实际比赛中，SAM 的构建代码长、调错困难，所以如果只是参加一般算法竞赛，二分+哈希往往是性价比更高的选择。

4.3 算法选型的决策参考

遇到这种题先别急着开写，看一眼数据范围再决定用哪个方案。我整理了一张选型表，直接照着选就行：

别小看这张表。我见过太多人拿着哈希方法去做小规模数据，代码写得又臭又长，最后还没 DP 快。反过来，也有人拿着 DP 去跑 10 万级数据，跑半天出不来结果。数据范围决定算法，这是解题的第一直觉。

5. 实际应用场景：这题不只是在竞赛里刷分

最长公共子串听起来很理论，但它实实在在出现在很多工程任务里。我把平时做过的几个典型场景列出来，方便大家理解这题的实用价值。

5.1 文本查重与相似度定位

论文查重、代码查重、商品描述查重的核心环节，往往都需要抽取“连续相同片段”。拿两段文本对比，找到最长的连续相同片段长度，再除以总长度，就能得到一个基础的相似度分数。这个指标比单纯统计词频要可靠得多，因为它抓住了“逐字搬用”的特征。

代码查重时更有意思。把代码去掉所有空白和注释之后，按字符数组处理，然后跑一遍最长公共子串，能精确定位哪些行的内容是重复拷贝过去的。很多查重系统会进一步把超过阈值长度的公共子串全部标记出来，而不只是最长的那一段。这个场景下，二维 DP 的 dp 表其实很有用，因为表里出现的每一个高值点都是一段相似片段的候选。

5.2 生物信息学中的序列比对

DNA 和蛋白质序列的比较是字符串算法的经典应用场景。生物学上，两条序列之间共享一段较长的连续相同片段，往往意味着这段序列在进化上高度保守，可能对应某个重要的功能区域。算法上，这就是典型的最长公共子串问题。

真实基因序列动辄几百万字符，直接跑 O(n*m) 是不现实的，所以工业界会使用后缀数组、FM-index 等更激进的数据结构。但比赛和面试的简化版用最长公共子串来理解序列共性是没问题的。你甚至可以写一个小脚本，把两条 DNA 片段输入进去，快速找到它们共有的最长保守片段，再拿去数据库比对。

5.3 日志异常定位与相似请求聚合

在后端开发中，大量日志来自同一套代码框架，不同请求的日志结构相似、细节不同。为了把日志聚合成几个典型“模式”，我经常用公共子串计算两条日志的公共部分。如果公共子串长度占了较短日志的 80% 以上，基本可以判定这两条日志属于同一种模式，可以归并处理。

更进一步，当线上出现大规模重复异常日志时，不同节点、不同时间的报错里往往共享同一段异常堆栈。抓出最长公共子串，就能快速判断“所有节点是不是挂在同一个调用链上”。这个场景下不一定需要字母级别精确，有时把日志按行切分，每一行当成一个“字符”，再做最长公共子串，效果反而更好。

6. 常见问题与排查技巧实录

写这题的人多，踩坑的人更多。我把这些年见过的典型错误整理成一个速查表，方便大家定位问题。

6.1 高频翻车现场速查表

6.2 对拍测试：用一个暴力解法做基准

我每次写完这类算法，一定会做对拍测试，不过程序的核心逻辑没问题。所谓对拍，就是写一个极其简单但一定正确的暴力版本，再用随机数据把优化版本和暴力版本的结果进行比较。

暴力版本思路很简单：枚举 s1 的所有开始位置 i，再枚举所有结束位置 j，判断s1[i:j]是否出现在 s2 里，记录最长那一个。这个版本正确性一目了然，虽然慢，但因为只是测试数据，量级可以控制。然后随机生成几百组小写字母、数字混合字符串，长度从 1 到 50 不等，跑一轮对比。只要有一组结果不同，立刻把两个串和两个版本的差距打印出来，基本就能定位到是状态转移还是回溯逻辑出了问题。

这个习惯帮我节省了大量时间。尤其滚动数组版本刚写完时，pre和temp的顺序搞反是常事，肉眼很难发现，但一拍就出来了。

6.3 我自己的调试心得

最后一个建议，也是我个人的习惯：调试动态规划问题时，小数据上打印 dp 表是最快的方式。拿s1 = "abcde"、s2 = "bcd"这种小样例，把 dp 表一行行打出来，你会看见一条清晰的对角线。这一步做完，整个转移过程就刻在脑子里了，之后写任何变体都不容易出错。

如果打印出来的表里对角线断了或者多出了不该有的数字，那就顺着值最大的格子往回查，看它的左上角是不是正确的连续值。这种“肉眼验证状态表”的方法，比单纯读代码有效得多。

另外建议大家养成一个习惯：把这题和“最长公共子序列”“编辑距离”放在一起对比复习。它们共享同一套 dp 表的思考框架，但每个都有自己独特的转移约束。对比着学，记忆会深很多，面试时被问到变体题也更容易变通。三分治七分练，最长公共子串这种基础题，写到条件反射才算真掌握。