1. 问题拆解与核心思路1.1 子串和子序列一字之差天壤之别最长公共子串Longest Common Substring这个经典问题我在刷字符串专项时反复遇到过很多次。题目编号 3508 这道题表面上就是给你两个字符串找出它们共同拥有的最长连续段但真正把它做透你会发现它串起了动态规划、后缀自动机、后缀数组、二分哈希这四大字符串利器。很多人第一眼会把它和最长公共子序列搞混这俩一个要求连续、一个只要求顺序一致解法完全是两个世界。举个例子s1 abcdes2 abfde。它们的最长公共子序列是 abde长度 4因为子序列允许跳着选只要相对顺序不变就行但最长公共子串只有 ab长度 2因为两个串里真正连续且相同的段只有开头这两个字符。这个区别不是小细节它直接决定了动态规划的转移方程、自动机的匹配策略和整个题目的思考方向。1.2 为什么暴力法不行以及两条优化主线先看最直接的暴力思路枚举第一个字符串的所有起点和终点每得到一个子串就去第二个字符串里匹配一次。子串数量是 O(n²)每次匹配 O(m)总复杂度 O(n²m)。假设两个串长度都是 1000那就是十亿这个数量级的字符比较本机跑都费劲OJ 的时限基本不可能放过。从暴力到高效本质上只有两条路一条是把反复比较子串这件事变成填表或者自动机匹配用空间换时间另一条是把找最长变成二分配合哈希在 O(1) 时间内验证某个长度是否可行。下面几节就是沿着这两条主线展开的。我个人建议把四种解法都吃透因为它们在面试手撕、竞赛限时、工程落地的场景里各有优势不是随便挑一个就够用的。2. 动态规划最直观也最稳妥的解法2.1 状态定义为什么必须以 i 和 j 结尾动态规划的第一步是定义状态。求最长公共子串时我们定义 dp[i][j] 表示以 s1 的第 i 个字符结尾、同时以 s2 的第 j 个字符结尾的公共子串的最大长度。注意这里的关键词是以……结尾它保证了这个公共段在两边的连续位置完全对齐。如果你把状态定义成前 i 个字符和前 j 个字符之间的最长公共子串长度那整个问题就变质了最后求出来的其实是子序列的长度或者一个不伦不类的中间量。为什么必须两个字符串同时考虑结尾因为公共子串是连续的一段它在 s1 里的最后一个字符和 s2 里的最后一个字符必须相同且位置对应。只有当 s1[i] s2[j] 时这一段才能从 dp[i-1][j-1] 延伸过来一旦字符不等连续性断了dp[i][j] 直接清零。这个断掉就归零的规则是子串问题和子序列问题最核心的分水岭。2.2 转移方程与答案还原转移方程写出来很简洁若 s1[i-1] s2[j-1]则 dp[i][j] dp[i-1][j-1] 1否则 dp[i][j] 0答案不是 dp[n][m]而是整个表里的最大值。这是因为公共子串可能出现在两个串的任意位置不一定要用满整个字符串。如果题目要求输出子串本身需要在更新最大值时记下当时的 i即 s1 里的结束位置最后用 s1.substr(endPos - maxLen, maxLen) 还原。标准实现如下#include bits/stdc.h using namespace std; string longestCommonSubstring(const string a, const string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); int maxLen 0, endPos 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; endPos i; } } } } return a.substr(endPos - maxLen, maxLen); }我习惯用 1-based 下标开 dp 表第 0 行第 0 列全部初始化为 0。这样 i0 或 j0 的边界情况自动被吸收进初始值里不用单独写判断代码干净不少。2.3 滚动数组降空间但别踩覆盖的坑二维 DP 的空间是 O(nm)当两个字符串长度到 10⁴ 量级时10⁸ 个 int 大约是 400MBOJ 直接爆内存。好在 dp[i][j] 只依赖 dp[i-1][j-1]也就是上一行的前一列所以用一维数组滚动即可。这里有个非常隐蔽的坑按行从左往右更新时dp[j-1] 已经被当前行的新值覆盖了再用它做转移就错了。正确做法是用临时变量 prev 保存上一行的 dp[j-1] 旧值string longestCommonSubstring2(const string a, const string b) { int n a.size(), m b.size(); vectorint dp(m 1, 0); int maxLen 0, endPos 0; for (int i 1; i n; i) { int prev 0; // 相当于 dp[i-1][0] for (int j 1; j m; j) { int temp dp[j]; // dp[j] 此刻还是 dp[i-1][j] if (a[i - 1] b[j - 1]) { dp[j] prev 1; if (dp[j] maxLen) { maxLen dp[j]; endPos i; } } else { dp[j] 0; } prev temp; // 留给下一轮使用 } } return a.substr(endPos - maxLen, maxLen); }这个坑我踩过不止一次。第一次写滚动数组时偷懒没存 temp直接用 dp[j-1] 转移结果几个长 case 全部错得离谱最后一步步打 log 才发现是旧值被覆盖了。记一个口诀要从上一行取值先备份再更新。注意DP 解法虽然好写但 n、m 超过 10⁵ 时O(nm) 的时间复杂度本身就是瓶颈了。这时候必须请出线性算法。3. 后缀自动机把复杂度压到 O(n)3.1 用大白话理解后缀自动机后缀自动机Suffix Automaton简称 SAM是一个能接收一个字符串所有子串的最小状态 DFA。它最漂亮的性质是构造复杂度 O(n)却能精确刻画所有子串之间的后缀关系。用它求最长公共子串的思路非常巧妙先对第一个字符串建 SAM再拿第二个字符串在 SAM 上滚动匹配过程中维护当前能匹配上的最长长度这个变量随时更新答案。很多初学者第一次看 SAM 都觉得难这里给一个直觉。SAM 由两类核心信息组成转移边 nxt 和后缀链接 link。转移边像字典树的边决定下一个字符能走到哪个状态后缀链接像一个回退指针从当前状态指向它最长后缀对应的状态。匹配时如果当前字符走不通就顺着 link 不断回退直到能走通或者退回根节点。这个过程实际上就是不断丢弃匹配串的前缀、保留尽可能长的可匹配后缀和 KMP 失配时跳 next 数组是同一套思维。3.2 建 SAM 与匹配的完整模板下面这份模板可以直接照着抄。S 是主串T 是要匹配的串。extend 负责逐个字符扩展 SAMquery 在 SAM 上跑 T 并返回最长公共子串长度struct SuffixAutomaton { vectorarrayint, 26 nxt; vectorint link, len; int last; SuffixAutomaton(int n 0) { nxt.reserve(2 * n 5); link.reserve(2 * n 5); len.reserve(2 * n 5); nxt.push_back({}); link.push_back(-1); len.push_back(0); last 0; } void extend(int c) { int cur nxt.size(); nxt.push_back({}); link.push_back(0); len.push_back(len[last] 1); int p last; while (p ! -1 !nxt[p][c]) { nxt[p][c] cur; p link[p]; } if (p -1) { link[cur] 0; } else { int q nxt[p][c]; if (len[p] 1 len[q]) { link[cur] q; } else { int clone nxt.size(); nxt.push_back(nxt[q]); link.push_back(link[q]); len.push_back(len[p] 1); while (p ! -1 nxt[p][c] q) { nxt[p][c] clone; p link[p]; } link[q] link[cur] clone; } } last cur; } int query(const string t) { int v 0, l 0, ans 0; for (char ch : t) { int c ch - a; while (v ! 0 !nxt[v][c]) { v link[v]; l len[v]; } if (nxt[v][c]) { v nxt[v][c]; l; } ans max(ans, l); } return ans; } }; int longestCommonSubstringSAM(const string s, const string t) { SuffixAutomaton sam(s.size()); for (char ch : s) sam.extend(ch - a); return sam.query(t); }匹配逻辑再说细一点v 是当前状态l 是从某个位置到当前字符为止能匹配上的公共段长度。每来一个新字符先尝试走转移边走不通就顺着 link 回退回退时把 l 重置为 len[v]因为后缀链接指向的状态代表当前匹配串的一个更短后缀。如果回到根节点还是走不了说明这个字符在 s 里根本没出现过l 直接清零。整个过程均摊 O(|T|)非常舒服。3.3 SAM 的时空复杂度与字符集权衡SAM 能做到线性原因在于两点每次 extend 最多新建两个状态cur 和 clone所以总状态数不超过 2n - 1匹配时每次回退 link 都会让 l 减小而 l 的总增加量不超过 |T|所以回退次数均摊有界。这种摊还分析是理解 SAM 性能的关键。空间上要重点说一句上面的模板用 arrayint, 26每个状态固定 26 个转移比较吃内存。n 为 10⁵ 时大约 2n × 26 × 4 字节约 20MB一般 OJ 能扛住但如果字符集很大或者字符串含中文建议换成 mapint,int 或 unordered_map牺牲单次查询的 log 换取灵活性和空间。注意SAM 是这四种解法里学习曲线最陡的但一旦掌握它就是处理子串问题的大杀器后面做最长重复子串、不同子串个数都会用上。4. 后缀数组 LCP经典路线再回首4.1 拼接串与 height 数组的妙用后缀数组Suffix Array求最长公共子串的思路也很经典用分隔符把两个串拼成一个串比如 s1 # s2然后求拼接串的后缀数组和 height 数组。height[i] 表示排名相邻的两个后缀的最长公共前缀 LCP。核心结论是两个原串之间的最长公共子串一定等于某个来自 s1 的后缀和某个来自 s2 的后缀的 LCP因此我们只需要扫描所有相邻后缀对取那些分属两个原串的对的 height 最大值。为什么扫描相邻对就够了假设最优的公共子串由后缀 u属于 s1和后缀 v属于 s2的 LCP 产生它们在 SA 中的位置是 p q。从 p 到 q 的区间里后缀归属一定会从 s1 切换到 s2那么必然存在至少一对相邻后缀分属两个串。在区间内取最小值的 height 等于这对最优后缀的 LCP所以区间内每个 height 都不小于它其中那对跨串相邻后缀的 height 自然也不会小于最优值。既然是最大值它恰好就等于最优值。这个证明想通了整个算法也就通了。4.2 倍增构造模板与扫描答案后缀数组我用倍增法复杂度 O(n log n)。构造和求 height 的代码可以直接复用vectorint buildSA(const string s) { int n s.size(); vectorint sa(n), rk(n), tmp(n); for (int i 0; i n; i) { rk[i] s[i]; sa[i] i; } for (int k 1; k n; k 1) { auto cmp [](int x, int y) { if (rk[x] ! rk[y]) return rk[x] rk[y]; int rx x k n ? rk[x k] : -1; int ry y k n ? rk[y k] : -1; return rx ry; }; sort(sa.begin(), sa.end(), cmp); tmp[sa[0]] 0; for (int i 1; i n; i) { tmp[sa[i]] tmp[sa[i - 1]] (cmp(sa[i - 1], sa[i]) ? 1 : 0); } rk tmp; if (rk[sa[n - 1]] n - 1) break; } return sa; } vectorint buildHeight(const string s, const vectorint sa) { int n s.size(); vectorint rk(n), height(n); for (int i 0; i n; i) rk[sa[i]] i; int k 0; for (int i 0; i n; i) { if (rk[i] 0) { k 0; continue; } int j sa[rk[i] - 1]; while (i k n j k n s[i k] s[j k]) k; height[rk[i]] k; if (k) --k; } return height; }拿到 height 数组后扫描一遍相邻对即可得到答案int longestCommonSubstringSA(const string a, const string b) { string s a # b; int n a.size(); vectorint sa buildSA(s); vectorint height buildHeight(s, sa); int ans 0; for (int i 1; i (int)s.size(); i) { bool cross (sa[i - 1] n sa[i] n) || (sa[i - 1] n sa[i] n); if (cross) ans max(ans, height[i]); } return ans; }注意分隔符 # 绝不能出现在两个原串里否则会破坏后缀排序的正确性。如果输入串可能包含任意可见字符建议用一个更冷僻的字符或者干脆换思路。后缀数组这条路实现细节比 SAM 多但它能顺带解决很多其他问题比如不同子串个数、最长重复子串属于学会一个受益一串的路线。5. 二分 滚动哈希工程上最省事的方案5.1 哈希判重的整体框架第四种方案是二分答案长度 L然后判断两个串是否存在长度为 L 的公共子串。判断方式是把 s1 中所有长度为 L 的子串的哈希值放进一个 unordered_set再对 s2 中所有长度为 L 的子串求哈希逐个查表命中就说明存在。这个做法的复杂度是 O((nm)log n)实现起来比 SAM 和后缀数组都简单得多而且完全不受字符集限制处理中文、二进制数据都没问题。配合滚动哈希前缀能在 O(1) 时间内取任意子串的哈希值。整体框架如下typedef unsigned long long ull; const int BASE 13331; struct RollHash { vectorull h, pw; RollHash(const string s) { int n s.size(); h.resize(n 1); pw.resize(n 1); pw[0] 1; for (int i 1; i n; i) { h[i] h[i - 1] * BASE s[i - 1]; pw[i] pw[i - 1] * BASE; } } ull get(int l, int r) { return h[r 1] - h[l] * pw[r - l 1]; } }; bool check(const RollHash h1, const RollHash h2, int L, int n, int m) { unordered_setull seen; for (int i 0; i L n; i) seen.insert(h1.get(i, i L - 1)); for (int j 0; j L m; j) { if (seen.count(h2.get(j, j L - 1))) return true; } return false; } int longestCommonSubstringHash(const string a, const string b) { int n a.size(), m b.size(); RollHash h1(a), h2(b); int lo 1, hi min(n, m), ans 0; while (lo hi) { int mid (lo hi) / 2; if (check(h1, h2, mid, n, m)) { ans mid; lo mid 1; } else { hi mid - 1; } } return ans; }5.2 碰撞规避与二分边界单模 ull 自然溢出在大多数 OJ 数据下能过但我确实吃过一次亏有人专门构造了针对自然溢出的数据单哈希直接 WA。稳妥的做法是双哈希即同时用两个模数组合比如 1e97 和 1e99或者一个质数模数 一个 ull 自然溢出组合两个哈希值都相等才认为子串相同。代价是多算一遍哈希时间约翻倍但在关键比赛中值得。二分的边界也要留神下界应从 1 开始如果连长度为 1 的公共子串都不存在答案是 0。我见过有人从 0 开始二分check(0) 永远返回 true导致二分区间的收缩逻辑出问题最后死循环或者答案差一。另外如果字符串只有小写字母BASE13331 完全够用如果是中文或二进制数据底数要大于最大字符编码值否则哈希值的区分度会急剧下降。注意unordered_set 在部分 OJ 上可能被精心构造的数据卡成 O(n)如果发现 TLE 且自认算法复杂度没问题建议换成 vector 排序后二分查找或者改用双模数加强后再试。6. 方案选型对比6.1 复杂度对照表四种主流解法的复杂度特性汇总如下解法时间复杂度空间复杂度学习曲线建议使用场景动态规划O(nm)O(m) 可优化最低n、m 不超过 10³追求稳妥后缀自动机 SAMO(nm)O(n × 字符集)较高n、m 达到 10⁵ 以上竞赛主力后缀数组 LCPO((nm)log(nm))O(nm)中高需要顺带解决其他后缀问题二分 滚动哈希O((nm)log n)O(nm)最低快速实现、处理 Unicode 数据这里的时间复杂度都是常规情况。空间复杂度一栏里 DP 写的是 O(m)指滚动数组优化后的结果SAM 的 O(n × 字符集) 是固定 26 数组版本的占用如果用 map 则约 O(n log 字符集)。6.2 什么时候选哪种我的个人决策习惯是这样的如果题目里两个字符串长度都在 2000 以内直接上 DP代码短、逻辑稳几乎不可能写错如果长度到了 10⁵ 级别首选 SAM线性复杂度最安心而且我可以直接复用模板如果是在真实工程项目里处理大文本或者输入包含中文、Unicode我会用二分 滚动哈希因为它不依赖字符集、思路容易向同事解释如果刚好是在复习后缀数组的专题那就顺手用后缀数组 LCP 解决还能一鱼多吃。没有绝对的最好算法只有最适配当前约束的算法。题做多了你会发现字符串题最值钱的不是背模板而是能在看到数据范围的那一刻就快速判断该上哪套工具。7. 常见错误与排查实录7.1 DP 下标的经典错误用 DP 时最容易犯的错是把状态定义记成前 i 个字符和前 j 个字符的最长公共子串长度。一旦这么写转移方程就会不自觉地往子序列的方向偏最后答案也不对。根源在于连续这个约束没有被编码进状态里。每次写代码前先问自己一句dp[i][j] 是不是以第 i 个、第 j 个字符结尾的公共段长度想清楚这句一半的坑就避开了。输出子串时注意记录的是 s1 的结束位置 endPos不是任意位置。如果存在多个长度相同的最长公共子串题目没特别要求就取第一个遇到的要求字典序最小的话需要把候选全部收集起来排序不能偷懒。7.2 SAM 的边界情况处理SAM 的坑主要在 extend 的 clone 分支。有些简化版教程省略了 len[p] 1 len[q] 的特判直接 clone结果结构错乱匹配结果莫名其妙差一截。另外query 里回退循环的条件必须是 v ! 0 !nxt[v][c]如果把 v ! 0 漏掉根节点的空转移会让程序死循环。我调试 SAM 时有个土办法很管用构造完整后对整棵自动机做一次 DFS统计从根出发能走出的路径总数它应该正好等于 n * (n 1) / 2也就是全部不同子串的数量。这个数字对不上说明构造代码有 bug逐个分支排查非常高效。7.3 哈希碰撞与超时排查二分 哈希出现 WA 时八成是碰撞出现 TLE 时先怀疑 unordered_set 被卡。针对碰撞换双哈希或加二次确认针对超时把 unordered_set 换成 vector sort 二分查找或者改用 Sahay 的排序思路往往立竿见影。这里要特别提醒unordered_set 的 O(1) 期望是建立在哈希函数均匀的假设下恶意构造的数据完全可以让它退化到 O(n)。工程上如果允许一点点性能损耗我还会在哈希命中后做一次真实的字符串比较确认把碰撞概率压到零。这种做法在安全第一的生产环境里很常见。8. 应用场景与扩展思考8.1 现实中的最长公共子串问题这个算法并不仅仅是 OJ 上的刷题套路。生物信息学里DNA 序列比对经常要找两条序列的最长公共片段用来判断同源关系代码查重系统把连续抄袭片段识别为公共子串日志分析里找多条错误记录中的重复模式也是同一个模型。很多看似不相关的实际问题剥开外壳都是这个核心问题。8.2 从两个串推广到多个串如果题目升级成k 个字符串的最长公共子串思路不变但实现要改。用 SAM 的话先对第一个串建 SAM然后让其余 k-1 个串分别在上面跑匹配每个状态维护来自每个串的最长匹配长度最后取所有状态上这些值的最小值的最大值。用后缀数组的话则在拼接串上做滑动窗口保证窗口内覆盖全部 k 个串。这种推广在面试中很常见从双串版本出发去推导多串版本逻辑会顺很多。最后再分享一点个人体会这四种解法之所以值得反复琢磨是因为它们背后的思维模型各不相同——DP 教你用结尾位置表达连续性SAM 教你用自动机状态压缩子串集合后缀数组教你用排序和 LCP 描述相似度哈希则教你用概率和二分折中复杂度。我自己刷字符串题最大的收获不是记住了哪个模板而是养成了一个习惯每次遇到找公共/重复/最长的题目先想清楚连续还是不连续、单串还是多串、n 有多大再决定上哪套武器。这个思考顺序比任何模板都更能帮你稳定通过测试。
最长公共子串算法详解：动态规划、后缀自动机、后缀数组与二分哈希
1. 问题拆解与核心思路1.1 子串和子序列一字之差天壤之别最长公共子串Longest Common Substring这个经典问题我在刷字符串专项时反复遇到过很多次。题目编号 3508 这道题表面上就是给你两个字符串找出它们共同拥有的最长连续段但真正把它做透你会发现它串起了动态规划、后缀自动机、后缀数组、二分哈希这四大字符串利器。很多人第一眼会把它和最长公共子序列搞混这俩一个要求连续、一个只要求顺序一致解法完全是两个世界。举个例子s1 abcdes2 abfde。它们的最长公共子序列是 abde长度 4因为子序列允许跳着选只要相对顺序不变就行但最长公共子串只有 ab长度 2因为两个串里真正连续且相同的段只有开头这两个字符。这个区别不是小细节它直接决定了动态规划的转移方程、自动机的匹配策略和整个题目的思考方向。1.2 为什么暴力法不行以及两条优化主线先看最直接的暴力思路枚举第一个字符串的所有起点和终点每得到一个子串就去第二个字符串里匹配一次。子串数量是 O(n²)每次匹配 O(m)总复杂度 O(n²m)。假设两个串长度都是 1000那就是十亿这个数量级的字符比较本机跑都费劲OJ 的时限基本不可能放过。从暴力到高效本质上只有两条路一条是把反复比较子串这件事变成填表或者自动机匹配用空间换时间另一条是把找最长变成二分配合哈希在 O(1) 时间内验证某个长度是否可行。下面几节就是沿着这两条主线展开的。我个人建议把四种解法都吃透因为它们在面试手撕、竞赛限时、工程落地的场景里各有优势不是随便挑一个就够用的。2. 动态规划最直观也最稳妥的解法2.1 状态定义为什么必须以 i 和 j 结尾动态规划的第一步是定义状态。求最长公共子串时我们定义 dp[i][j] 表示以 s1 的第 i 个字符结尾、同时以 s2 的第 j 个字符结尾的公共子串的最大长度。注意这里的关键词是以……结尾它保证了这个公共段在两边的连续位置完全对齐。如果你把状态定义成前 i 个字符和前 j 个字符之间的最长公共子串长度那整个问题就变质了最后求出来的其实是子序列的长度或者一个不伦不类的中间量。为什么必须两个字符串同时考虑结尾因为公共子串是连续的一段它在 s1 里的最后一个字符和 s2 里的最后一个字符必须相同且位置对应。只有当 s1[i] s2[j] 时这一段才能从 dp[i-1][j-1] 延伸过来一旦字符不等连续性断了dp[i][j] 直接清零。这个断掉就归零的规则是子串问题和子序列问题最核心的分水岭。2.2 转移方程与答案还原转移方程写出来很简洁若 s1[i-1] s2[j-1]则 dp[i][j] dp[i-1][j-1] 1否则 dp[i][j] 0答案不是 dp[n][m]而是整个表里的最大值。这是因为公共子串可能出现在两个串的任意位置不一定要用满整个字符串。如果题目要求输出子串本身需要在更新最大值时记下当时的 i即 s1 里的结束位置最后用 s1.substr(endPos - maxLen, maxLen) 还原。标准实现如下#include bits/stdc.h using namespace std; string longestCommonSubstring(const string a, const string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); int maxLen 0, endPos 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; endPos i; } } } } return a.substr(endPos - maxLen, maxLen); }我习惯用 1-based 下标开 dp 表第 0 行第 0 列全部初始化为 0。这样 i0 或 j0 的边界情况自动被吸收进初始值里不用单独写判断代码干净不少。2.3 滚动数组降空间但别踩覆盖的坑二维 DP 的空间是 O(nm)当两个字符串长度到 10⁴ 量级时10⁸ 个 int 大约是 400MBOJ 直接爆内存。好在 dp[i][j] 只依赖 dp[i-1][j-1]也就是上一行的前一列所以用一维数组滚动即可。这里有个非常隐蔽的坑按行从左往右更新时dp[j-1] 已经被当前行的新值覆盖了再用它做转移就错了。正确做法是用临时变量 prev 保存上一行的 dp[j-1] 旧值string longestCommonSubstring2(const string a, const string b) { int n a.size(), m b.size(); vectorint dp(m 1, 0); int maxLen 0, endPos 0; for (int i 1; i n; i) { int prev 0; // 相当于 dp[i-1][0] for (int j 1; j m; j) { int temp dp[j]; // dp[j] 此刻还是 dp[i-1][j] if (a[i - 1] b[j - 1]) { dp[j] prev 1; if (dp[j] maxLen) { maxLen dp[j]; endPos i; } } else { dp[j] 0; } prev temp; // 留给下一轮使用 } } return a.substr(endPos - maxLen, maxLen); }这个坑我踩过不止一次。第一次写滚动数组时偷懒没存 temp直接用 dp[j-1] 转移结果几个长 case 全部错得离谱最后一步步打 log 才发现是旧值被覆盖了。记一个口诀要从上一行取值先备份再更新。注意DP 解法虽然好写但 n、m 超过 10⁵ 时O(nm) 的时间复杂度本身就是瓶颈了。这时候必须请出线性算法。3. 后缀自动机把复杂度压到 O(n)3.1 用大白话理解后缀自动机后缀自动机Suffix Automaton简称 SAM是一个能接收一个字符串所有子串的最小状态 DFA。它最漂亮的性质是构造复杂度 O(n)却能精确刻画所有子串之间的后缀关系。用它求最长公共子串的思路非常巧妙先对第一个字符串建 SAM再拿第二个字符串在 SAM 上滚动匹配过程中维护当前能匹配上的最长长度这个变量随时更新答案。很多初学者第一次看 SAM 都觉得难这里给一个直觉。SAM 由两类核心信息组成转移边 nxt 和后缀链接 link。转移边像字典树的边决定下一个字符能走到哪个状态后缀链接像一个回退指针从当前状态指向它最长后缀对应的状态。匹配时如果当前字符走不通就顺着 link 不断回退直到能走通或者退回根节点。这个过程实际上就是不断丢弃匹配串的前缀、保留尽可能长的可匹配后缀和 KMP 失配时跳 next 数组是同一套思维。3.2 建 SAM 与匹配的完整模板下面这份模板可以直接照着抄。S 是主串T 是要匹配的串。extend 负责逐个字符扩展 SAMquery 在 SAM 上跑 T 并返回最长公共子串长度struct SuffixAutomaton { vectorarrayint, 26 nxt; vectorint link, len; int last; SuffixAutomaton(int n 0) { nxt.reserve(2 * n 5); link.reserve(2 * n 5); len.reserve(2 * n 5); nxt.push_back({}); link.push_back(-1); len.push_back(0); last 0; } void extend(int c) { int cur nxt.size(); nxt.push_back({}); link.push_back(0); len.push_back(len[last] 1); int p last; while (p ! -1 !nxt[p][c]) { nxt[p][c] cur; p link[p]; } if (p -1) { link[cur] 0; } else { int q nxt[p][c]; if (len[p] 1 len[q]) { link[cur] q; } else { int clone nxt.size(); nxt.push_back(nxt[q]); link.push_back(link[q]); len.push_back(len[p] 1); while (p ! -1 nxt[p][c] q) { nxt[p][c] clone; p link[p]; } link[q] link[cur] clone; } } last cur; } int query(const string t) { int v 0, l 0, ans 0; for (char ch : t) { int c ch - a; while (v ! 0 !nxt[v][c]) { v link[v]; l len[v]; } if (nxt[v][c]) { v nxt[v][c]; l; } ans max(ans, l); } return ans; } }; int longestCommonSubstringSAM(const string s, const string t) { SuffixAutomaton sam(s.size()); for (char ch : s) sam.extend(ch - a); return sam.query(t); }匹配逻辑再说细一点v 是当前状态l 是从某个位置到当前字符为止能匹配上的公共段长度。每来一个新字符先尝试走转移边走不通就顺着 link 回退回退时把 l 重置为 len[v]因为后缀链接指向的状态代表当前匹配串的一个更短后缀。如果回到根节点还是走不了说明这个字符在 s 里根本没出现过l 直接清零。整个过程均摊 O(|T|)非常舒服。3.3 SAM 的时空复杂度与字符集权衡SAM 能做到线性原因在于两点每次 extend 最多新建两个状态cur 和 clone所以总状态数不超过 2n - 1匹配时每次回退 link 都会让 l 减小而 l 的总增加量不超过 |T|所以回退次数均摊有界。这种摊还分析是理解 SAM 性能的关键。空间上要重点说一句上面的模板用 arrayint, 26每个状态固定 26 个转移比较吃内存。n 为 10⁵ 时大约 2n × 26 × 4 字节约 20MB一般 OJ 能扛住但如果字符集很大或者字符串含中文建议换成 mapint,int 或 unordered_map牺牲单次查询的 log 换取灵活性和空间。注意SAM 是这四种解法里学习曲线最陡的但一旦掌握它就是处理子串问题的大杀器后面做最长重复子串、不同子串个数都会用上。4. 后缀数组 LCP经典路线再回首4.1 拼接串与 height 数组的妙用后缀数组Suffix Array求最长公共子串的思路也很经典用分隔符把两个串拼成一个串比如 s1 # s2然后求拼接串的后缀数组和 height 数组。height[i] 表示排名相邻的两个后缀的最长公共前缀 LCP。核心结论是两个原串之间的最长公共子串一定等于某个来自 s1 的后缀和某个来自 s2 的后缀的 LCP因此我们只需要扫描所有相邻后缀对取那些分属两个原串的对的 height 最大值。为什么扫描相邻对就够了假设最优的公共子串由后缀 u属于 s1和后缀 v属于 s2的 LCP 产生它们在 SA 中的位置是 p q。从 p 到 q 的区间里后缀归属一定会从 s1 切换到 s2那么必然存在至少一对相邻后缀分属两个串。在区间内取最小值的 height 等于这对最优后缀的 LCP所以区间内每个 height 都不小于它其中那对跨串相邻后缀的 height 自然也不会小于最优值。既然是最大值它恰好就等于最优值。这个证明想通了整个算法也就通了。4.2 倍增构造模板与扫描答案后缀数组我用倍增法复杂度 O(n log n)。构造和求 height 的代码可以直接复用vectorint buildSA(const string s) { int n s.size(); vectorint sa(n), rk(n), tmp(n); for (int i 0; i n; i) { rk[i] s[i]; sa[i] i; } for (int k 1; k n; k 1) { auto cmp [](int x, int y) { if (rk[x] ! rk[y]) return rk[x] rk[y]; int rx x k n ? rk[x k] : -1; int ry y k n ? rk[y k] : -1; return rx ry; }; sort(sa.begin(), sa.end(), cmp); tmp[sa[0]] 0; for (int i 1; i n; i) { tmp[sa[i]] tmp[sa[i - 1]] (cmp(sa[i - 1], sa[i]) ? 1 : 0); } rk tmp; if (rk[sa[n - 1]] n - 1) break; } return sa; } vectorint buildHeight(const string s, const vectorint sa) { int n s.size(); vectorint rk(n), height(n); for (int i 0; i n; i) rk[sa[i]] i; int k 0; for (int i 0; i n; i) { if (rk[i] 0) { k 0; continue; } int j sa[rk[i] - 1]; while (i k n j k n s[i k] s[j k]) k; height[rk[i]] k; if (k) --k; } return height; }拿到 height 数组后扫描一遍相邻对即可得到答案int longestCommonSubstringSA(const string a, const string b) { string s a # b; int n a.size(); vectorint sa buildSA(s); vectorint height buildHeight(s, sa); int ans 0; for (int i 1; i (int)s.size(); i) { bool cross (sa[i - 1] n sa[i] n) || (sa[i - 1] n sa[i] n); if (cross) ans max(ans, height[i]); } return ans; }注意分隔符 # 绝不能出现在两个原串里否则会破坏后缀排序的正确性。如果输入串可能包含任意可见字符建议用一个更冷僻的字符或者干脆换思路。后缀数组这条路实现细节比 SAM 多但它能顺带解决很多其他问题比如不同子串个数、最长重复子串属于学会一个受益一串的路线。5. 二分 滚动哈希工程上最省事的方案5.1 哈希判重的整体框架第四种方案是二分答案长度 L然后判断两个串是否存在长度为 L 的公共子串。判断方式是把 s1 中所有长度为 L 的子串的哈希值放进一个 unordered_set再对 s2 中所有长度为 L 的子串求哈希逐个查表命中就说明存在。这个做法的复杂度是 O((nm)log n)实现起来比 SAM 和后缀数组都简单得多而且完全不受字符集限制处理中文、二进制数据都没问题。配合滚动哈希前缀能在 O(1) 时间内取任意子串的哈希值。整体框架如下typedef unsigned long long ull; const int BASE 13331; struct RollHash { vectorull h, pw; RollHash(const string s) { int n s.size(); h.resize(n 1); pw.resize(n 1); pw[0] 1; for (int i 1; i n; i) { h[i] h[i - 1] * BASE s[i - 1]; pw[i] pw[i - 1] * BASE; } } ull get(int l, int r) { return h[r 1] - h[l] * pw[r - l 1]; } }; bool check(const RollHash h1, const RollHash h2, int L, int n, int m) { unordered_setull seen; for (int i 0; i L n; i) seen.insert(h1.get(i, i L - 1)); for (int j 0; j L m; j) { if (seen.count(h2.get(j, j L - 1))) return true; } return false; } int longestCommonSubstringHash(const string a, const string b) { int n a.size(), m b.size(); RollHash h1(a), h2(b); int lo 1, hi min(n, m), ans 0; while (lo hi) { int mid (lo hi) / 2; if (check(h1, h2, mid, n, m)) { ans mid; lo mid 1; } else { hi mid - 1; } } return ans; }5.2 碰撞规避与二分边界单模 ull 自然溢出在大多数 OJ 数据下能过但我确实吃过一次亏有人专门构造了针对自然溢出的数据单哈希直接 WA。稳妥的做法是双哈希即同时用两个模数组合比如 1e97 和 1e99或者一个质数模数 一个 ull 自然溢出组合两个哈希值都相等才认为子串相同。代价是多算一遍哈希时间约翻倍但在关键比赛中值得。二分的边界也要留神下界应从 1 开始如果连长度为 1 的公共子串都不存在答案是 0。我见过有人从 0 开始二分check(0) 永远返回 true导致二分区间的收缩逻辑出问题最后死循环或者答案差一。另外如果字符串只有小写字母BASE13331 完全够用如果是中文或二进制数据底数要大于最大字符编码值否则哈希值的区分度会急剧下降。注意unordered_set 在部分 OJ 上可能被精心构造的数据卡成 O(n)如果发现 TLE 且自认算法复杂度没问题建议换成 vector 排序后二分查找或者改用双模数加强后再试。6. 方案选型对比6.1 复杂度对照表四种主流解法的复杂度特性汇总如下解法时间复杂度空间复杂度学习曲线建议使用场景动态规划O(nm)O(m) 可优化最低n、m 不超过 10³追求稳妥后缀自动机 SAMO(nm)O(n × 字符集)较高n、m 达到 10⁵ 以上竞赛主力后缀数组 LCPO((nm)log(nm))O(nm)中高需要顺带解决其他后缀问题二分 滚动哈希O((nm)log n)O(nm)最低快速实现、处理 Unicode 数据这里的时间复杂度都是常规情况。空间复杂度一栏里 DP 写的是 O(m)指滚动数组优化后的结果SAM 的 O(n × 字符集) 是固定 26 数组版本的占用如果用 map 则约 O(n log 字符集)。6.2 什么时候选哪种我的个人决策习惯是这样的如果题目里两个字符串长度都在 2000 以内直接上 DP代码短、逻辑稳几乎不可能写错如果长度到了 10⁵ 级别首选 SAM线性复杂度最安心而且我可以直接复用模板如果是在真实工程项目里处理大文本或者输入包含中文、Unicode我会用二分 滚动哈希因为它不依赖字符集、思路容易向同事解释如果刚好是在复习后缀数组的专题那就顺手用后缀数组 LCP 解决还能一鱼多吃。没有绝对的最好算法只有最适配当前约束的算法。题做多了你会发现字符串题最值钱的不是背模板而是能在看到数据范围的那一刻就快速判断该上哪套工具。7. 常见错误与排查实录7.1 DP 下标的经典错误用 DP 时最容易犯的错是把状态定义记成前 i 个字符和前 j 个字符的最长公共子串长度。一旦这么写转移方程就会不自觉地往子序列的方向偏最后答案也不对。根源在于连续这个约束没有被编码进状态里。每次写代码前先问自己一句dp[i][j] 是不是以第 i 个、第 j 个字符结尾的公共段长度想清楚这句一半的坑就避开了。输出子串时注意记录的是 s1 的结束位置 endPos不是任意位置。如果存在多个长度相同的最长公共子串题目没特别要求就取第一个遇到的要求字典序最小的话需要把候选全部收集起来排序不能偷懒。7.2 SAM 的边界情况处理SAM 的坑主要在 extend 的 clone 分支。有些简化版教程省略了 len[p] 1 len[q] 的特判直接 clone结果结构错乱匹配结果莫名其妙差一截。另外query 里回退循环的条件必须是 v ! 0 !nxt[v][c]如果把 v ! 0 漏掉根节点的空转移会让程序死循环。我调试 SAM 时有个土办法很管用构造完整后对整棵自动机做一次 DFS统计从根出发能走出的路径总数它应该正好等于 n * (n 1) / 2也就是全部不同子串的数量。这个数字对不上说明构造代码有 bug逐个分支排查非常高效。7.3 哈希碰撞与超时排查二分 哈希出现 WA 时八成是碰撞出现 TLE 时先怀疑 unordered_set 被卡。针对碰撞换双哈希或加二次确认针对超时把 unordered_set 换成 vector sort 二分查找或者改用 Sahay 的排序思路往往立竿见影。这里要特别提醒unordered_set 的 O(1) 期望是建立在哈希函数均匀的假设下恶意构造的数据完全可以让它退化到 O(n)。工程上如果允许一点点性能损耗我还会在哈希命中后做一次真实的字符串比较确认把碰撞概率压到零。这种做法在安全第一的生产环境里很常见。8. 应用场景与扩展思考8.1 现实中的最长公共子串问题这个算法并不仅仅是 OJ 上的刷题套路。生物信息学里DNA 序列比对经常要找两条序列的最长公共片段用来判断同源关系代码查重系统把连续抄袭片段识别为公共子串日志分析里找多条错误记录中的重复模式也是同一个模型。很多看似不相关的实际问题剥开外壳都是这个核心问题。8.2 从两个串推广到多个串如果题目升级成k 个字符串的最长公共子串思路不变但实现要改。用 SAM 的话先对第一个串建 SAM然后让其余 k-1 个串分别在上面跑匹配每个状态维护来自每个串的最长匹配长度最后取所有状态上这些值的最小值的最大值。用后缀数组的话则在拼接串上做滑动窗口保证窗口内覆盖全部 k 个串。这种推广在面试中很常见从双串版本出发去推导多串版本逻辑会顺很多。最后再分享一点个人体会这四种解法之所以值得反复琢磨是因为它们背后的思维模型各不相同——DP 教你用结尾位置表达连续性SAM 教你用自动机状态压缩子串集合后缀数组教你用排序和 LCP 描述相似度哈希则教你用概率和二分折中复杂度。我自己刷字符串题最大的收获不是记住了哪个模板而是养成了一个习惯每次遇到找公共/重复/最长的题目先想清楚连续还是不连续、单串还是多串、n 有多大再决定上哪套武器。这个思考顺序比任何模板都更能帮你稳定通过测试。
