最长公共子串长度这个题目看起来人畜无害背地里却栽过不少人。上周我帮一位朋友看代码他信心满满地用动态规划写了一个求两个字符串公共子串的函数结果拿abc和ababc一测返回 1。问题出在哪出在他把子串的状态转移方程写成了子序列的写法。这种错误太常见了常见到我认为有必要把这题的完整思路从头捋一遍。这篇文章我会从暴力解法一路写到滚动数组优化再把中文字符、Unicode 这类工程层面的坑也交代清楚。不管你是准备面试还是要在文本查重、序列比对项目里用到这个算法都值得花十分钟读完。1. 子串和子序列一字之差结果天壤之别拿到题目第一步不是写代码而是把概念抠干净。“子串”要求在原字符串中连续出现比如abcde的子串有abc、bcd、de但没有ace“子序列”只要求保持相对顺序不要求连续所以ace就是abcde的子序列。一字之差算法模型完全不同。很多人一看到“最长公共子串”下意识就想到动态规划课本里的最长公共子序列英文缩写还都是 LCS于是直接把子序列的转移方程套过来结果差之毫厘谬以千里。我见过不止一次有人用子序列的 dp 做子串跑出来的长度比正确答案大许多放到查重系统里两篇不相干的文章会被判定成高度相似。举一个直观的例子s1 abcdefs2 abxcdf最长公共子串是ab或cd长度都是 2。为什么cdf不算因为c、d、f在s1中不连续中间隔了一个e。最长公共子序列是abcdf长度 5因为a、b、c、d、f在两个字符串里按顺序出现即可。同样是“公共”的东西长度从 2 跳到 5差了两倍多。如果你的业务逻辑是找连续重复片段比如代码查重、日志相似度用子序列算法会严重误报。先确认需求要的是“连续片段”还是“允许跳字符的相似匹配”再决定算法。对比项最长公共子串最长公共子序列连续性要求必须连续只要求顺序不要求连续状态转移字符相等时dp[i][j] dp[i-1][j-1] 1dp[i][j] dp[i-1][j-1] 1状态转移字符不等时dp[i][j] 0dp[i][j] max(dp[i-1][j], dp[i][j-1])时间复杂度O(n*m)O(n*m)典型场景查重、DNA 保守片段、diff基因序列比对、文本 diff 底层模型这篇文章要讨论的“最长公共子串长度”所有代码和推导都围绕“连续”这两个字展开。2. 暴力解它给了动态规划最重要的直觉先说最直观的暴力方法也是很多新手第一反应能想到的枚举s1的所有子串用字符串匹配检查它是否在s2中出现。s1长度为n子串数量是 O(n^2)每个子串做一次包含判断是 O(m)总复杂度 O(n^2 * m)。如果为了判断再把所有子串存下来空间也直接爆炸。这个方案只配在玩具数据上跑。真正值得写的是另一种暴力双指针同步扩展。对s1的每个起始位置i和s2的每个起始位置j从这两个位置同时向后比较统计能连续匹配多长。用 C 写出来长这样int longestCommonSubstringBrute(const string s1, const string s2) { int n s1.size(), m s2.size(); int best 0; for (int i 0; i n; i) { for (int j 0; j m; j) { int k 0; while (i k n j k m s1[i k] s2[j k]) { k; } best max(best, k); } } return best; }这段代码的正确性很好验证它枚举了所有可能的“公共子串起点”组合然后一路吃到匹配不动为止。最坏情况是两个完全相同的长字符串比如s1和s2都是 10 万个a每次while都要走到字符串末尾总复杂度 O(n^2 * min(n,m))约等于 O(n^3)跑一次能让你等到怀疑人生。但我不建议直接跳过暴力不写原因有两个。第一它是动态规划的思想原型暴力里的“从(i,j)开始向后连续匹配”等价于动态规划里的“以s1[i]和s2[j]结尾的连续段长度”。你只是把重复的比较结果缓存起来就得到了 dp 表。第二暴力可以加剪枝如果当前best已经大于等于剩余可匹配长度提前break虽然改变不了最坏复杂度但很多真实数据下能快不少。从暴力到 dp 的演进本质是用一张表换掉重复比较。暴力的每次while循环都在反复比较同一对字符而 dp 表保证每一对字符只被计算一次。3. 动态规划核心为什么 dp[i][j] 只从左上角来3.1 状态定义一定是“以某个字符结尾”的后缀状态定义必须咬文嚼字dp[i][j]表示“以s1的第i个字符作为结尾同时以s2的第j个字符作为结尾”的最长公共子串长度。等价地说dp[i][j]是s1[0..i-1]和s2[0..j-1]的最长公共后缀的长度。为什么要限定后缀而不是任意公共子串因为只有后缀才是连续的。当s1[i-1] s2[j-1]的时候新的公共子串要想延长必须接在上一段连续段后面而上一段连续段必须以s1[i-2]和s2[j-2]结尾正好就是dp[i-1][j-1]。如果当前字符不相等说明以这两个位置结尾的连续匹配段不存在直接置 0。状态转移方程如下if (s1[i-1] s2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] 0; }这里用 1-based 索引把dp[0][j]和dp[i][0]留作哨兵 0。很多新手写二维 dp 时喜欢用 0-based然后被边界条件折磨得手忙脚乱用 1-based 加哨兵代码干净也不容易越界。3.2 手动填一张表胜过背十遍公式拿s1 abcde、s2 abxde手动填一遍表感受会更直接0abxde0000000a010000b002000c000000d000010e000002右下角dp[5][5] 2表示以s1的e和s2的e结尾最长公共后缀是de长度 2。整个 dp 矩阵里的最大值就是答案这里也是 2。再和子序列的转移对比一次关键就在“字符不等”这一行。子序列允许跳过字符所以不匹配时还能继承左边或上边的值子串不允许跳过一旦断了就清零。很多错误实现就是把max(dp[i-1][j], dp[i][j-1])那一行抄了过来导致断掉的连续段被重新“续”上长度虚高这就是开头那个abc匹配出 1 的根源。Java 实现如下public int longestCommonSubstring(String s1, String s2) { int n s1.length(), m s2.length(); int[][] dp new int[n 1][m 1]; int maxLen 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1] 1; maxLen Math.max(maxLen, dp[i][j]); } else { dp[i][j] 0; } } } return maxLen; }时间复杂度 O(nm)空间 O(nm)。几千个字符的字符串完全没问题但要是有人给你几 MB 的文本内存就不太够了。这就是下一节要解决的事。4. 一维数组优化正序遍历为什么必错4.1 空间能压缩的原因dp[i][j]只依赖dp[i-1][j-1]也就是说当前行只需要上一行的信息和更早的行无关。所以理论上只要一个长度为m的一维数组就够了。于是很多人写出了这样的朴素版本public int longestCommonSubstringWrong(String s1, String s2) { int n s1.length(), m s2.length(); int[] dp new int[m 1]; int maxLen 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[j] dp[j - 1] 1; maxLen Math.max(maxLen, dp[j]); } else { dp[j] 0; } } } return maxLen; }这段代码看起来逻辑清晰可惜是错的。用s1 abc、s2 ababc实测正确结果是 3最长公共子串是abc这段代码只会返回 1。这不是精度问题而是彻底算错了。4.2 反例走查看看正序到底错在哪一步错的原因要从滚动数组的本质讲起。二维表中更新dp[i][j]时需要的是上一轮i-1行的dp[i-1][j-1]也就是“前一行、前一列”的值。但在正序遍历的一维数组里dp[j-1]已经被当前这一轮第i行更新过了它现在是“当前行、前一列”的值。拿它做转移等于把一个基于s1[i-1]的匹配段和另一个同样基于s1[i-1]的匹配段首尾拼接逻辑上完全讲不通。我把这个反例的错乱过程展开。s1 abcs2 ababc一维数组初始全是 0。第一轮i1s1[0]aj12345s2 字符ababcdp[j] 更新后10100第二轮i2s1[1]bj12345s2 字符ababcdp[j] 更新后01010第三轮i3s1[2]c关键就在这一轮j12345s2 字符ababc正序更新前的 dp[j]01010正序更新后的 dp[j]00001第三轮j5时s1[2]c和s2[4]c匹配本来应该取二维表里的dp[2][4] 2再加 1 得到 3。但正序遍历下dp[4]已经在当前轮的j4被重置成了 0于是只能得到 1。这就是一维滚动数组优化里最经典的坑。二维版本完全不会错因为dp[2][4]和dp[3][4]存在不同的格子里互不覆盖。4.3 两种正确写法解决方案一是从后往前遍历j。更新dp[j]的时候dp[j-1]还是上一轮的值它恰好就是二维表里的dp[i-1][j-1]。public int longestCommonSubstringOptimized(String s1, String s2) { int n s1.length(), m s2.length(); int[] dp new int[m 1]; int maxLen 0; for (int i 1; i n; i) { for (int j m; j 1; j--) { if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[j] dp[j - 1] 1; maxLen Math.max(maxLen, dp[j]); } else { dp[j] 0; } } } return maxLen; }解决方案二是用一个prev变量显式保存左上角的值。每行开始前prev 0内层循环里先记录temp dp[j]转移时使用prev最后prev temp。这种写法不依赖遍历顺序在需要同时维护多个数组的场景里更灵活public int longestCommonSubstringOptimizedPrev(String s1, String s2) { int n s1.length(), m s2.length(); int[] dp new int[m 1]; int maxLen 0; for (int i 1; i n; i) { int prev 0; for (int j 1; j m; j) { int temp dp[j]; if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[j] prev 1; maxLen Math.max(maxLen, dp[j]); } else { dp[j] 0; } prev temp; } } return maxLen; }两种写法我都实际验证过结果一致。面试时我个人更推荐从后往前那版代码最短也不容易在prev的更新时机上绕晕。如果你能顺手讲清楚prev方案里temp dp[j]保存的是上一行的值会很加分因为这说明你真懂滚动数组而不是背模板。空间优化后的复杂度是 O(n*m) 时间、O(m) 空间。注意如果m比n大很多可以先把两个字符串交换让m等于较短串的长度内存再省一截。5. 只求长度不够回溯出具体的最长公共子串真实业务里只有长度数字通常不够。比如文本查重时你得告诉用户“哪一段是重复的”而不是“重复了 20 个字符”。如果用的是二维 dp回溯非常方便。先扫一遍表找到最大值maxLen以及对应的行i然后直接从s1里截取子串即可不需要真的走对角线回溯。因为dp[i][j] maxLen时s1中以第i个字符结尾、长度为maxLen的子串就是答案。public String longestCommonSubstringTraceback(String s1, String s2) { int n s1.length(), m s2.length(); int[][] dp new int[n 1][m 1]; int maxLen 0; int endIndex 0; // 最长公共子串在 s1 中的结束位置 for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; endIndex i; } } else { dp[i][j] 0; } } } return s1.substring(endIndex - maxLen, endIndex); }注意 Java 的substring是左闭右开所以取endIndex - maxLen到endIndex。如果maxLen为 0substring(0, 0)是空串调用方要单独处理免得把空串当成非法值。如果存在多个长度相同的最长公共子串上面的写法只返回第一个遇到的结果。要全部拿到可以用一个列表记录所有满足dp[i][j] maxLen的i逐一截取并用Set去重。我在查重项目里实测过同一个子串可能从不同路径被记录多次去重这步不能省。顺带提醒如果用了滚动数组优化回溯能力基本就废了因为历史信息被覆盖。我的建议是只要需要具体子串就老老实实用二维 dp只有纯算长度时才用一维。不要为了省那点空间把代码复杂度拉满可读性也是生产力。对几万字符的中小型文本二维 dp 的内存完全够用。6. 工程实战中文、Unicode、超长文本怎么处理网上大多数教程讲完 dp 就收尾了但真实项目里还有几个坑迟早会碰上。6.1 中文字符和 emoji 的编码陷阱Java 的String.length()返回的是 UTF-16 的 code unit 数量。一个中文字符在基本平面内算 1但一个 emoji 会被编码成两个 code unitlength()等于 2。如果直接用charAt逐字符比较一个 emoji 会被拆成两个 char两个不同的 emoji 可能因为前半段代理相同而被误判成部分匹配。解决办法是按 Unicode 代码点处理先把字符串转换成int[]数组再在这个数组上跑 dp。int[] codePoints1 s1.codePoints().toArray(); int[] codePoints2 s2.codePoints().toArray();Python 在这块相对省心len()是 1字符串迭代天然按码点走。但如果维护的是老项目最好先确认字符串没有经过奇怪的转码否则 dp 的结果会出现“看起来差不多但长度对不上”的诡异问题。6.2 超长文本的工程选型假设两个字符串各有 10 万字符二维 dp 的 int 数组就是 10 万乘 10 万约 400 亿个 int内存直接爆掉。滚动数组虽然把空间降到 O(m)但时间还是 O(n*m)同样跑不动。工程上更常用的是另外两条路哈希加二分。对某个长度 k把s1的所有长度为 k 的子串哈希值放进哈希集合再检查s2的每个长度为 k 的子串哈希是否命中用二分去逼近最大可行 k。复杂度在 O(n log n) 量级实现适中是很多文本查重系统的选择。哈希碰撞可以用双哈希或命中后二次验证来规避。后缀自动机。构建s1的后缀自动机遍历s2在自动机上走转移并维护当前匹配长度走不通就沿后缀链接回退总复杂度 O(nm)是理论最优方案之一。代价是实现复杂、学习成本高但处理超大文本是首选。下面把常见方案放在一起对比方便按场景选方案时间复杂度空间复杂度优点缺点双指针暴力O(n^2*min(n,m))O(1)实现最简单数据一大就跑不动二维 dpO(n*m)O(n*m)易理解、可回溯内存占用大一维 dpO(n*m)O(m)空间省、可求长度回溯困难哈希加二分O(n log n)O(n)实现适中、可处理大文本有哈希碰撞风险后缀自动机O(nm)O(n)理论最优实现复杂、学习成本高第三个坑是应用场景的取舍。文本查重时通常不只看单条最长公共子串而是统计所有长度超过某个阈值的公共子串再用总长度或占比做相似度指标。这种需求用 dp 枚举所有最长结果会很笨更适合滑动窗口加阈值去重。代码相似度检测又不一样一般先做 token 化把变量名、空白、缩进全部归一化再对 token 序列求公共子串或子序列否则一行缩进差异就能掩盖真正的复用关系。算法题的标准答案和工程里的正确答案往往不是同一个东西把 dp 原理吃透再根据实际数据量选型这才是这个题目真正的价值所在。