企业官网建设流程全解析

最长公共子串这个题，算法圈里基本绕不过去。它考察的东西很密：连续子串的边界把握、动态规划的状态设计、空间优化，再到高阶算法里对字符串索引结构的理解。我平时在带新人、做代码评审时，也经常拿这个题当试金石，因为很多人能把二维 DP 写出来，但一追问"内存能不能省？字符串上万怎么办？"就卡住了。这篇文章想把这条链路完整串一遍，从基础 DP 到二分哈希、后缀数组、后缀自动机，最后落到实际选型和避坑上，算是这几年反复实践后的一次集中整理。

1. 问题定位与核心难点拆解

1.1 最长公共子串的准确定义

先抠定义。给定两个字符串 A 和 B，长度分别记为 n 和 m。公共子串要求的是一个字符序列，它同时是 A 中连续出现的一段，也是 B 中连续出现的一段。注意"连续"两个字，这是和"公共子序列"最大的区别。

举个经典例子：A = "banana"，B = "ananas"。这两个串的公共子串有 "ana"（长度 3）、"nan"（长度 3）等，最长长度就是 3。但如果你按子序列来算，"anana" 这种跨着跳的字符序列也能匹配上，长度能到 5，可它不连续，不算数。

这个区分直接决定了状态转移的写法。子序列问题里，状态可以"跳跃继承"上一行的值；而子串问题里，一旦字符不等，结果必须清零。很多刚上手的人就是没想通"清零"这个动作，导致最后求出来的答案其实是公共子序列长度。

另外还有一个容易混淆的概念：多个最长公共子串时，题目一般只问长度。如果要输出具体内容，就需要额外记录答案位置，这一点的代价比想象中高，我后面会专门展开。

1.2 暴力法到底慢在哪里

在进入动态规划之前，先看看暴力枚举方案的复杂度，方便后面理解优化的必要性。

最原始的想法是枚举 A 的起点 i 和 B 的起点 j，然后从这两个位置开始，逐字符向后比对，统计能连续匹配多长。每次比对最坏情况下要走到某一个字符串的末尾，代价是 O(min(n - i, m - j))。把所有起点组合都枚举一遍，最坏时间复杂度是：

O(n × m × min(n, m))

举个例子，两个字符串各 1000 个字符时，这个值大约是 10^9 级别的字符比较，现代机器跑起来也会明显卡顿；如果各 10000 字符，那基本就是天文数字了。

有人可能会想，用 KMP 之类的高效单串匹配算法能不能优化？很遗憾，KMP 只适合"模式串已知"的情况，而这里模式串本身是未知的，长度也是未知的，等于要在大量可能的模式串里找最长的那一个。所以需要换一个思路：把"模式串长度"这个变量通过某种索引结构或者动态规划一次性处理掉。

2. 动态规划解法：从二维表到空间优化

2.1 状态设计和转移方程

动态规划解决这类问题非常自然。定义一个二维数组 dp，其中 dp[i][j] 表示：以 A 的第 i 个字符结尾、B 的第 j 个字符结尾的公共子串的最大长度。

这里有一个大部分题解不会强调的点：为什么强调"以第 i 个字符结尾"？因为我们要保证连续。如果匹配到当前位置，前面也连续匹配过，那么当前子串自然而然就能延长一位；如果当前位置字符不等，那以这里结尾的公共连续子串根本不存在，长度就是 0。

状态转移分两种：

• 如果 A[i] == B[j]，则 dp[i][j] = dp[i-1][j-1] + 1
• 如果 A[i] != B[j]，则 dp[i][j] = 0

最终答案就是整个二维数组里的最大值。

以 A = "banana"、B = "ananas" 为例，某几个位置的 dp 值大致如下（只列出末尾匹配相关的行，方便观察）：

可以看到 dp[4][3] = 3，代表 "ana" 这条公共子串成立；dp[4][5] = 3 代表 "ana" 在 B 的另一个位置也成立。最大值就是 3。

这个转移里最关键的思想是"连续性"：我们只关心上一行左上角那个状态，而不是像子序列问题那样还要考虑左边和上边的状态。设计 DP 状态时，先问清楚"我要求的东西是不是必须以某个位置为终点"，比直接套模板重要得多。

2.2 滚动数组优化

二维 DP 的缺陷非常明显：空间复杂度是 O(n×m)。

当 n 和 m 都等于 1 万时，一个 int 二维数组占用 1万 × 1万 × 4 字节，约等于 400 MB；如果 n 和 m 都到 10 万，那就是 40 GB，普通服务器都撑不住。

好在观察转移方程可以发现，dp[i][j] 只依赖 dp[i-1][j-1]，也就是上一行、前一列的值。完全不需要保留整个二维数组，只需要保留上一行的一维结果，再配合当前行滚动计算即可。

改成滚动数组后，空间复杂度直接降到 O(m)。实现如下：

public int longestCommonSubstring(String a, String b) { int n = a.length(); int m = b.length(); int[] pre = new int[m + 1]; int[] cur = new int[m + 1]; int best = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) { cur[j] = pre[j - 1] + 1; best = Math.max(best, cur[j]); } else { cur[j] = 0; } } int[] tmp = pre; pre = cur; cur = tmp; } return best; }

这段代码有两个细节需要特别注意。

第一个细节：else 分支里必须显式把 cur[j] 清零。因为数组是复用的，cur 数组里可能残留上一轮循环的旧值。如果不清理，后续字符不等的位置就可能会出现一个"虚胖"的继承长度，导致答案错误。

第二个细节：不能用一维数组从右往左遍历来“省掉” pre/cur 两份。有人觉得只开一个数组、内层从右向左遍历，dp[j] = dp[j-1] + 1，这样也能模拟左上角状态，但实际上这和真正的滚动数组不是一回事。从右向左遍历时，dp[j-1] 会在同一次循环里被更新过，用它来推导 dp[j] 就变成了"斜向阶梯传播"，结果会和真实 DP 完全偏离。我见过不少人栽在这上面。

2.3 输出最长子串本身

很多场景只问长度，但也有一些场景需要把具体的公共子串打印出来。这里有个取舍：如果使用了完整的二维 DP，可以在记录最大值的那个位置 (i, j) 出发，沿对角线往回走，把匹配的字符收集起来再反转。因为二维表保留着所有历史状态，回溯路径是明确的。

但如果已经使用了滚动数组，历史状态已经被覆盖，无法再回溯。所以答案是：在更新 best 的第一时间，把 A 的结束下标 i、以及当时的 best 值记录到额外的变量里。最后只需要从 A 的 i - best + 1 位置截取到 i，就是那个最长公共子串。

如果存在多个相同长度的最长公共子串，想全部输出，那就需要记录所有达到 best 的终点下标，再去重截取。这个需求实际出现概率不高，但搞清楚实现思路，比临时到网上翻代码踏实得多。

我自己的建议是：新人阶段先用二维 DP 做一遍，能正确回溯后再改成滚动数组。直接上滚动数组虽然内存好看了，但如果连完整 DP 的转移逻辑都没吃透，遇到复杂一点的变种题容易懵。

3. 适应超长文本的三套进阶方案

当 n 和 m 增长到十万、百万级别，O(n×m) 的 DP 即使空间优化了，时间上也扛不住。这个时候需要跳出"逐格填表"的思路，从字符串结构本身找办法。下面三套方案是我在实际项目中反复用到的，各有优劣。

3.1 二分枚举长度 + 滚动哈希

这套方法的核心洞察是：最长公共子串的长度具有单调性。如果存在长度为 L 的公共子串，那么对于任意小于等于 L 的长度 k，也一定存在长度为 k 的公共子串，因为直接截取 L 的子串前面 k 个字符即可。

所以可以二分答案，把问题转化为"是否存在长度为 len 的公共子串"。

判定过程很简单：

• 计算 A 中所有长度为 len 的子串的哈希值，放进一个集合
• 遍历 B 中所有长度为 len 的子串，算哈希后去集合里查

如果查到了，说明长度为 len 的公共子串存在，二分区间往上收；否则往下收。总复杂度是 O((n + m) × log(min(n, m)))，空间复杂度 O(n) 或者 O(m)，在超大文本场景下非常实用。

哈希的计算要用滚动哈希，也就是利用前一个子串的哈希值在常数时间里推出下一个子串的哈希值，核心公式类似：

hash[i+1] = (hash[i] × base + s[i+1] - s[i-len] × base^len)

这里要小心几点。

第一，取模问题。用一个大质数取模，比如 10^9+7，单个哈希冲突概率已经比较低，但并非为零。如果题目或业务要求极高的正确性，建议使用双哈希，即用两个不同的模数或基数算两次，把两个哈希值拼成一个 key 去查。

第二，固定 base 容易被构造数据卡掉。在比赛或者安全要求较高的场景，建议在程序启动时用随机数生成 base，让攻击者无法提前构造碰撞。

第三，一旦哈希命中，理论上还存在假阳性可能。严格的实现应该再对原始字符串做一次真实比对确认，尤其是在医疗数据、专利文本这类对错误零容忍的场景里。

3.2 后缀数组 + 高度数组

后缀数组是处理字符串匹配问题的一把利器。思路这样来：把 A 和 B 拼接成一个长串，中间插入一个不会在原文里出现的分隔符，比如 '#'：

C = A + '#' + B

然后求 C 的后缀数组 sa 和高度数组 height。height[i] 表示排名第 i 个后缀和排名第 i-1 个后缀的最长公共前缀长度。

任意两个后缀的最长公共前缀，都是它们在排序后相邻区间的 height 最小值。而两个字符串的最长公共子串，等价于从 A 内部取一个后缀、从 B 内部取一个后缀，它们的最长公共前缀的最大值。加上分隔符之后，公共前缀不会越界，所以只需要扫描一遍 height 数组：

• 如果 height[i] 大于当前答案，再判断参与比较的两个后缀是否一个来自 A、一个来自 B
• 如果是，答案更新为 height[i]

这个方法的关键在于"分隔符不会出现在原串中"。实际选择分隔符时，要注意原字符串的字符集。如果处理的是纯 ASCII 文本，用 '#' 就行；如果处理的是任意字节串，可以考虑用两个字符组合作为分隔符，或者先对字符集做映射，确保分隔符唯一且不会碰撞。

后缀数组实现难度比 DP 高，尤其是倍增排序的代码细节多，但我建议至少能把模板背下来、说清楚原理。因为它不止能解决公共子串，还能顺带解决很多字符串问题，像最长回文子串的 Manacher 不方便处理的一些场景，也可以借助后缀数组和 height 来另辟蹊径。

时间复杂度主要取决于后缀数组的构建。倍增法是 O((n+m) log(n+m))，空间 O(n+m)，对于百万级别文本完全能接受。

3.3 后缀自动机

后缀自动机可能是三种进阶方案里抽象程度最高的一种，但它的时间复杂度最优：构建 B 的 SAM 是 O(m)，扫描 A 是 O(n)，整体线性。

后缀自动机的思路，可以粗糙理解为"用最紧凑的图结构，保存一个字符串的所有后缀信息"。构建完成后，从初始状态出发，沿转移边能走到的任意一条路径，都对应原串的某个子串。

扫描 A 过程如下：

• 用一个指针 p 指向当前 SAM 状态，维护变量 len 表示当前匹配到的公共子串长度
• 每读入 A 的一个字符 ch：
  • 如果状态 p 有转移边 ch，就沿边走过去，len 加 1
  • 如果没有转移，就沿着后缀链接向上跳，跳到某个祖先状态存在 ch 的转移为止
  • 如果跳到根节点还找不到，说明当前字符匹配不上，len 重置为 0，重新从根开始

答案就是整个扫描过程中 len 的最大值。

这里的"后缀链接"是理解 SAM 的难点，但它起的作用很像 KMP 里的失败指针：匹配失败时，不要从头开始，而是回退到当前已经匹配上的、更短的合法后缀，再尝试延续。SAM 靠着这个机制，保证每个字符最多被处理若干固定次数，所以整体是线性复杂度。

SAM 表面难，但其实实现起来比后缀数组还短。我在实际项目里需要处理上千万字符的两两比对时，优先用的就是 SAM。它的缺点在于概念门槛高，如果对 endpos 等价类、后缀链接这些没有理解，写出来的代码出错了很难调试。

4. 实测对比与工程选型建议

4.1 复杂度与内存对比

先把几种方案的期望表现摆到一起，方便对照。这里的数字是基于常规工程实现的大致水平，语言和环境不同会有浮动，主要看趋势。

空间方面要算一笔账。n = m = 10 万时，二维 int 数组约 40 GB，这在绝大多数开发机上直接失败；滚动数组只有 0.8 MB 左右，但时间仍要执行约 10^10 次字符比较，至少需要几十秒甚至几分钟量级。而 SAM 构建 B 的节点数不超过 2m，也就是 20 万节点，每个节点记录转移边和链接，总内存大约十几 MB，配合线性的扫描时间，优势非常明显。

4.2 我的选型建议

如果是在面试、教学或者做 LeetCode 类题目，优先选择滚动数组 DP。不是因为它最快，而是因为它足够简单、直观，而且能在几分钟内写出无 bug 的代码。面试官想考察的是你懂不懂连续性和状态转移，而不是你会不会背后缀数组模板。

如果是在处理真实业务文本，比如文章查重、日志相似度分析、基因序列比对之类的场景，我一般会这样选：

• 文本量在几万以内，直接用滚动数组 DP，简单可靠，不用考虑哈希碰撞
• 文本量达到几十万到几百万，优先用二分 + 双哈希。它实现中等，速度好，而且天然方便多线程分片
• 一对多场景，也就是一个长文本要反复和很多其他文本比对，建一次 SAM 或后缀数组索引比较划算
• 正确性要求极端严格的场景，请务必加上真实字符串二次校验，或者直接用后缀数组

这里补充一个容易被忽略的工程细节：哈希方法非常容易并行。把长文本按照片段切分，每个 worker 处理一段，最后汇总最大值，整个过程不需要复杂同步。这对现代多核服务器来说是很实际的加速手段。

4.3 从长度到内容的一层延伸

做完最长公共子串长度之后，很多人会自然想到一个衍生需求：相似度计算。直接用最长公共子串长度除以较短的字符串长度，能粗略表示两个文本的重合程度，但它的缺点是会把很长的单一重复片段权重放得过大。

更稳健的做法是计算最长公共子串的覆盖率，或者找到所有长度超过阈值的公共子串集合，再求并集占比。这个方向上，后缀数组的 height 数组很好用，因为它天然给出了所有相邻后缀的公共前缀长度，只要做一次阈值过滤，就能得到互不重叠的公共片段。我参与过一个内部文本聚类项目，最初就是只取了最大长度，结果两个只重合一句话的长文档被判断为高度相似，后来改成了覆盖率方案才正常。工程选型，从来没有银弹。

5. 实践中最容易踩到的坑

5.1 索引偏移与数组越界

DP 数组经常从 1 开始计数，方便处理 i-1 的边界，但字符串本身从 0 开始。这样写：

if (a.charAt(i - 1) == b.charAt(j - 1)) { cur[j] = pre[j - 1] + 1; }

如果直接写成 a.charAt(i)，会在 i 从 0 开始时出现越界；如果 DP 数组也按 0 开始，就需要单独处理 i=0 或 j=0 那一行，代码会更脏。统一使用"dp 下标 1 表示字符串第 0 个字符"这一映射关系，边角问题会少很多。

还有一种低级但常见的错误：循环把 j <= m 写成 j < m，导致最后一个字符永远不参与比较。对于长度恰好 1 的测试用例，结果会直接错误，而且这种 bug 在测试数据少时很难发现。

5.2 空串与边界条件

A 或者 B 为空时，最长公共子串长度是 0。滚动数组和二维 DP 对这个情况都能自然处理，但二分 + 哈希方案里计算子串哈希前要记得判断 min(n, m) == 0，直接返回 0，否则二分右边界会是 0 甚至负数，引起不必要的麻烦。

我建议写一个固定的边界测试集，至少包含这些用例：

• A 为空、B 为空
• A 与 B 完全相同
• A 与 B 完全无交集
• 只有一个字符，相同和不同各一组
• 最短长度为 1，分散出现在两串多个位置
• 两个字符串由同一个字符重复构成，比如 "aaaaa" 和 "aaaa"
• 只有最后一个字符相同，用来验证终点记录是否准确

这类边界用例在二分和哈希方案里尤其重要，因为答案的单调性和哈希集合操作容易掩盖边界漏洞。

5.3 字符集与大小写规则

算法本身只关心字符是否相等，但工程实践中字符集经常带来意外。大小写要不要区分？中英文混排时按字节比较还是按字符比较？如果输入是 URL 编码后的文本，要不要先解码？

如果是常规开发语言，比如 Java 的 char 是 UTF-16 编码单元，大多数常用字符可以直接比较。但遇到某些生僻字或 emoji 字符时，charAt 只能取到代理对的一半，直接比较就会出问题。更稳妥的做法是先用 code point 拆成整数数组，再跑算法；如果是中文为主的数据集，最简单省事的是直接操作字符串的字符数组，然后在测试集里加入中文重复片段。

大小写方面，看业务需求。日志分析一般要区分大小写，文章查重常常不区分。实现时不要写死在算法内部，应该把字符串预处理单独抽出来，统一转小写或者转大写后再比较。这样算法部分保持纯粹，后续改动也只在预处理处。

5.4 哈希碰撞的假阳性和性能误判

单哈希配合 unordered_set 看似美妙，但碰撞风险不是理论问题，而是实际操作里真的会遇到。我之前做一个相似文本过滤工具，就遇到过两条无关文本被判定为存在 20 字符长度的公共子串，一开始以为是数据问题，查了半天才发现是基数和模数选择不当导致哈希碰撞。

处理办法通常两种：

• 双哈希，把两个不同模数下的哈希值组合成 key，碰撞概率降到极低
• 哈希命中后，对命中的那段字符串做一次真实逐字符比对

真正对结果要求苛刻的系统，我会把两种都加上：先用哈希快速筛选候选，再对候选做精确验证。这样既保住速度，又从根上消除假阳性。

另外要提醒的是，二分 + 哈希方案里计算 base^len 要预处理好，避免循环里反复用快速幂。如果 base 取 131、模数取 10^9+7，在 64 位整数下直接做乘法再取模即可，但 base^len 的数组只用 O(log n) 或者预处理到最大长度即可，否则复杂度会退化。

最后说一个我自己的习惯。不管用哪种实现，我都会先跑一遍上面列的短测试集，确认逻辑没有边角问题，然后再用随机生成的长字符串做压测。最长公共子串题目看起来简单，但它真的是最容易在细节上翻车的经典题之一。把这些坑都踩一遍、填一遍，比盲目刷十几道同类题更有效。