“求两个字符串的最长公共子串长度”这个题目我估计很多人在面试和实际工程里都撞到过。名字和最长公共子序列LCS只差两个字但解法思路和代码细节完全是两码事很多新手上来就套LCS的模板结果死在“连续性”这个关键点上。这篇文章就专门聊这个题目从最直观的暴力解法讲到标准动态规划再到滚动数组优化最后进入多字符串扩展和真实应用场景。全文不只是贴代码更重要的是把每一步“为什么这么做”讲透配合我踩过的坑和排查思路让你看完能直接写出一份既正确又有含金量的实现。1. 先把题意拆清楚子串与子序列的致命区别1.1 看似微小的定义差异直接决定算法走向给定两个字符串 A 和 B最长公共子串要求的是在原字符串中连续出现的一段字符而最长公共子序列只要求保持相对顺序允许中间跳过其他字符。举个例子说明A abcdf B abcf最长公共子序列 LCS 是 abcf长度 4字符可以跳着取。最长公共子串长度是 3也就是 abc因为 B 里的 f 在 c 之后没错但在 A 里 c 与 f 之间隔了一个 d连续段不成立。这个例子我几乎每次讲这块都会用因为它足够小又能把“连续性”的约束暴露得清清楚楚。很多人一看名字相近第一反应就是“这不就是LCS吗改一个条件就行”结果真动手改的时候又发现差分数组、状态方程都有微妙变化很容易改出一半对一半错的东西。1.2 为什么工程上更常算“长度”而非“具体子串”实际业务里比如代码相似度检测、重复文本定位、日志模式提取、基因序列比对第一步往往只需要知道“最长匹配了多长”。如果一个匹配长度低于阈值比如 5 个字符基本可以忽略当作噪声。如果匹配长度超过阈值才会定位到具体位置再做上下文分析。先算长度还有一个好处长度量级小便于设定过滤条件避免存储大量临时子串。真要输出具体内容也要先确认最长长度到底是多少再回源字符串去截取避免在多处重复匹配时输出多个同样的子串造成数据膨胀。所以这个题“长度优先”的设计是非常贴合生产需求的。2. 从暴力法开始理解问题的最小可行实现2.1 所有起点组合都拆一遍的代价暴力法的核心思路很直接枚举 A 中每一个子串的起点再看这个子串是否出现在 B 里。伪代码如下maxLen 0 for i in 0..lenA-1: for j in 0..lenB-1: curLen 0 while icurLen lenA jcurLen lenB A[icurLen] B[jcurLen]: curLen // 字符相等就继续向右延伸 maxLen max(maxLen, curLen)说白了就是把 A 的每一个位置都当成“可能的起点”和 B 的每一个位置对齐然后拼命往右走直到字符对不上为止。这个做法能在几秒钟之内写完也绝对正确但性能很差。2.2 暴力法的时间复杂度推演对于长度分别为 m 和 n 的字符串外层两个循环枚举起点复杂度是 O(m·n)。内层 while 在极端情况下两个字符串完全相同每个起点组合都要跑出 O(min(m,n)) 的长度。总的时间复杂度是 O(m·n·min(m,n))。如果两个字符串都是 1000 长度外层组合数就是 100 万每个组合还要再延伸接近 1000 次最坏情况就是 10 亿次字符比较。在一般语言里这已经需要几秒甚至几十秒了。要是字符串升到 1 万长度这个暴力法基本是跑不完的。暴力法存在的价值不是让你交付而是让你验证动态规划实现的正确性。我工程上经常先写一个暴力版做基准再拿它对比优化版跑随机数据只要结果一致说明状态转移逻辑没写偏这是一个非常实用的自测思路。3. 动态规划标准解法二维表的构建与状态推导3.1 DP 定义和状态转移方程定义状态dp[i][j] 以 A 的第 i 个字符结尾、且以 B 的第 j 个字符结尾的公共子串的最大长度注意这里的描述**“以当前字符结尾”**是这个题的重点。它意味着dp[i][j]只描述那些从某个位置开始、恰好延伸到(i,j)的连续匹配段。相应的状态转移方程if A[i] B[j]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 0这个方程的含义非常直观如果当前字符相等就说明可以在前一个字符的公共子串后面多接一个字符所以是dp[i-1][j-1] 1。如果当前字符不等那么“以这两个位置结尾的公共连续段”根本不存在所以直接置为 0。其中dp[i-1][j-1]表示以 A 的前一个字符和 B 的前一个字符结尾的公共子串长度这是保证连续性的关键。一旦出现“不等”的情况就把这一格清零而不是像最长公共子序列那样保留前面的候选值。这里必须补一个细节真正两个字符串的下标是从 0 开始的但为了编写代码方便通常把 dp 数组尺寸设为(m1) x (n1)第 0 行第 0 列作为辅助边界值恒为 0。这样dp[i][j]才对应A[i-1]和B[j-1]的比较。3.2 二维 DP 表的可视化以A abcde、B abfce为例构造 DP 表abfce000000a010000b002000c000010d000000e000001可以看到匹配到 ab 的时候dp[2][2]等于 2因为它是从dp[1][1]递推过来的而 c 和 e 的匹配长度只有 1因为它们的对角线前缀并不连续没有形成更长的链条。这张表做出来以后你会发现一个规律最长公共子串长度就是整个 dp 表里的最大值。因为每个格子都描述一个“以某对字符结尾的”子串长度最长的那一段必然对应某个结尾位置。这个结论也让我们实现的时候只需要全程维护一个全局最大值变量即可。3.3 标准代码实现Pythondef longest_common_substring_len(A: str, B: str) - int: m, n len(A), len(B) if m 0 or n 0: return 0 dp [[0] * (n 1) for _ in range(m 1)] max_len 0 for i in range(1, m 1): for j in range(1, n 1): if A[i - 1] B[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 if dp[i][j] max_len: max_len dp[i][j] # 字符不等时 dp[i][j] 本来就是 0无需额外赋值 return max_len这里有个地方可以提一下性能当m和n都在 1000 以内时这个二维 DP 是秒出的但如果两边都到 10000二维数组光是存储就需要 1 亿个整数内存开销就是数百 MB。所以下一步的滚动数组优化几乎是必然要讲的。3.4 各语言实现要点差异用 Java 实现时二维数组要用int[][] dp new int[m1][n1]初始值默认全是 0不需要额外初始化辅助行列。用 C 则建议使用vectorvectorint既方便又安全避免裸指针在长度相等或为空时的越界问题。还有一个容易被忽略的边界如果两个字符串里有一个是空串直接返回 0。这个判断放在函数最开始能省掉一堆后续的越界问题和特殊分支判断。很多现场写代码的人一上来就开二维数组结果空串输入直接崩在访问s[0]上这种低级错误在面试中非常致命。4. 进阶核心空间压缩与滚动数组实现4.1 为什么可以压缩成一维数组观察状态转移方程会发现dp[i][j]只依赖dp[i-1][j-1]。这是一个对角线依赖也就是当前格只与左上方的格子有关。如果按普通的从左到右、从上到下的遍历顺序更新dp[j]时原来的dp[j-1]已经被这一行覆盖了此时要拿它代表上一行的dp[i-1][j-1]就不对了。所以遍历时必须从右往左更新这样dp[j-1]还是上一行的旧值还没有被覆盖。这种从右往左的更新方式也让我联想到背包问题里的滚动数组优化。两者本质上都是“在状态只依赖上一行某位置时用一维数组反向遍历来保留旧值”的经典套路。理解了这一层后面无论遇到什么DP压缩题都能触类旁通。4.2 滚动数组版本代码def longest_common_substring_len_optimized(A: str, B: str) - int: m, n len(A), len(B) if m 0 or n 0: return 0 # 选择较短的字符串作为列方向进一步减少内存 if m n: A, B B, A m, n n, m dp [0] * (n 1) max_len 0 for i in range(1, m 1): for j in range(n, 0, -1): if A[i - 1] B[j - 1]: dp[j] dp[j - 1] 1 max_len max(max_len, dp[j]) else: dp[j] 0 return max_len这里我把较短字符串放到列方向n数组大小只跟它有关进一步压缩了内存。两个字符串长度差很大的时候比如一个是几万行日志片段一个是几百字符的关键字这个优化效果非常明显。4.3 时间与空间复杂度对比方案时间复杂度空间复杂度适用场景暴力法O(m·n·min(m,n))O(1)极短字符串、验证正确性二维 DPO(m·n)O(m·n)m,n ≤ 2000 左右滚动数组 DPO(m·n)O(min(m,n))一个字符串很长需要控内存后缀数组/后缀自动机O(mn) 构建、O(mn) 查询O(mn)超长文本、重复模式挖掘后缀数组和 SAM 属于竞赛和工程进阶方案普通业务需求用滚动数组 DP 就已经非常够用。真到了基因序列几十万上百万长度的时候再考虑这些复杂结构不迟。5. 多字符串扩展从二元到多元的转变5.1 多字符串最长公共子串的朴素思路如果问题从“两个字符串”变成“k 个字符串”要求找出这些字符串中共同出现的最长连续片段长度思路并不复杂主要有两种扩展方向方向一逐对合并先求第 1、2 个字符串的公共子串集合再把结果作为虚拟字符串与第 3 个字符串求公共子串依此类推。但这里必须小心多字符串的交集结果可能会断裂每一轮合并不一定保留完整连续段所以这种思路需要额外维护“候选子串集合”而非只留一个长度。方向二枚举种子并验证取最短字符串枚举它的所有子串或每个后缀的前缀去其他 k-1 个字符串里逐一看是否是子串。这个思路实现简单但时间复杂度不低适合 k 比较小的场景。方向三基于后缀数组 二分长度把所有字符串拼接成一个长串中间用特殊分隔符隔开然后构建后缀数组通过检查连续区间里是否包含所有原始字符串的后缀前缀再二分公共长度这是竞赛里处理多字符串 LCS 的经典手段。这个方案实现复杂度高但性能和稳定性都很优秀。5.2 一个实际可用的多串 DP 扩展如果 k 很小且字符串都不长可以用多维 DP 直接求解。三字符串的转移方程变成if A[i] B[j] C[k]: dp[i][j][k] dp[i-1][j-1][k-1] 1 else: dp[i][j][k] 0三维 DP 的空间是 O(m·n·p)三个字符串各 500 长度时就会到 1.25 亿个格内存压力很大所以实际工程中我更推荐“取最短串、枚举后缀前缀”的思路。用 KMP 或字符串哈希去快速判断子串是否在其他字符串中出现编码量适中也能扛住数百长度的输入。我做一个多语言文本查重的小工具时就是先对所有文档按长度排序取最短的文档枚举“连续片段候选”再用滚动哈希快速去其他文档中验证整体效果不错。这类“以最小集合为基准、哈希加速验证”的思路在相似度计算和重复内容检测里非常通用。6. 实际应用场景与案例复盘6.1 场景一代码相似度检测检测两个源码文件是否有抄袭嫌疑最直接的特征就是寻找较长的公共连续片段。把源码做简单预处理去掉空行、注释、把变量名归一化。对 Token 序列跑最长公共子串算法。只要最长匹配长度占总代码长度的比例超过阈值比如 20%就标记为高危。我在一个内部代码审计工具里实践过这个小功能。单文件代码几千 Token 规模滚动数组 DP 只需几十毫秒完全够用。而如果用完整的语法树比较反而功能冗余、开销大不适合做粗筛最长公共子串长度作为“第一道闸门”非常合适。6.2 场景二基因与序列比对生物信息学里常见的局部比对场景就是找两条序列中最相似的连续片段。直接使用最长公共子串长度能快速判断两条序列是否存在同源片段。DNA 序列由 A/T/C/G 组成长度动不动就是几万甚至百万。在这种规模下普通 O(m·n) DP 就不太够看了一般会结合后缀自动机或 BWT 索引算法。不过如果数据是经过分段截取的“局部序列片段”长度几千以内DP 方案依然可以胜任。6.3 场景三日志异常与重复模式发现运维场景里大量重复日志往往意味着某类异常正在高频发生。把日志逐行切分后连续相同片段就是重复模式预定义最小匹配长度如 20 字符低于阈值直接忽略。求最长公共子串长度如果多次出现且长度稳定说明是周期性输出需要重点关注。再结合时间戳和频率做根因分析。这种玩法在日志聚类、监控告警压缩上非常有效。我遇到过一个案例线上服务疯狂打印同一段堆栈单靠关键字抓取很容易漏而用公共子串长度计算所有日志两两之间的相似度然后聚合最相似的日志簇很快就定位到了问题点。6.4 场景四抄袭检测与内容查重查重系统内部通常不会拿原始全文直接匹配而是先提取“指纹序列”再做局部最长匹配。最长公共子串长度可以量化“连续抄袭片段”的严重程度。比如处理新闻报道类文本时“连续抄袭 100 字以上”比“零散搬运 300 字”更有判定说服力因为前者意味着大段复制粘贴后者可能只是引用不当。这个思路也是很多内容平台原创度检测背后的基础逻辑。7. 常见问题与排查技巧实录7.1 现象结果总是比预期小很多原因多半是把“子串”和“子序列”的状态定义混淆了在字符不等时依然沿用了max(dp[i-1][j], dp[i][j-1])的写法。解决方法字符不等时直接置 0不做任何“继承”。我刚开始写这个题也犯过这个错后来通过随机暴力对比才发现问题所以强烈建议写完先跑一轮暴力基准验证。7.2 现象滚动数组更新后结果不对原因遍历方向弄错。如果从左往右更新dp[j-1]已经是本轮覆盖过的新值对角依赖被破坏结果必然错误。解决方法内层循环必须从n到1反向遍历。这个坑非常高发甚至很多面经答案都没写对写代码时一定要盯着遍历方向。7.3 现象内存占用过高甚至 OOM原因直接上二维 DP且两个字符串都很长。解决方法切换到滚动数组版本再把较短的字符串放到列方向这样空间复杂度直接降为 O(min(m,n))。7.4 现象边界字符匹配不出来原因下标处理不一致。常见错误是dp[i][j]对应A[i]和B[j]但 i 或 j 正好是 0访问到字符串开头的前一个字符导致越界。解决方法统一约定“dp[i][j] 表示以 A[i-1] 与 B[j-1] 结尾的公共子串长度”用n1列多出来的一列全是 0 作为哨兵这样可以彻底规避负下标问题。7.5 现象多字符串扩展后结果包含断裂片段原因求长度时没有维护连续性子串在中间断开结果错误地连到了一起。解决方法多字符串场景下要么使用三维 DP 保证连续性要么维护候选连续段并逐串验证不能仅靠两两 LCS 拼接。8. 参数选择与工程调优经验8.1 如何确定“算长度”还是“回溯源字符串”在实践中具体子串非常重要但通常不需要把所有匹配段都记下来只需要记录最大长度和对应的结束下标。当全局最大值更新时把(i, j)记下来算完后再用A[i-maxLen:i]回溯出结果。这样既避免了大数组存储又能在事后随时取出内容。def longest_common_substring_with_result(A: str, B: str) - str: m, n len(A), len(B) dp [[0] * (n 1) for _ in range(m 1)] max_len 0 end_idx 0 for i in range(1, m 1): for j in range(1, n 1): if A[i - 1] B[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 if dp[i][j] max_len: max_len dp[i][j] end_idx i - 1 else: dp[i][j] 0 return A[end_idx - max_len 1: end_idx 1]这个带返回值的版本比单纯返回长度更实用。很多真实业务场景比如日志定位和文本查重拿到长度以后还是得知道具体是哪一段内容才好做后续分析。8.2 阈值设置技巧工程中很少直接输出“最长公共子串长度”一般都是配合阈值过滤噪声。比如文本指纹检测时长度小于 10 的匹配几乎没什么意义基因序列片段比对时匹配长度至少要大于 30 个碱基才认为是有意义的同源片段。阈值需要结合具体领域的数据分布来定先统计分析一批真实数据再根据结果设定合理分位点比拍脑袋靠谱得多。遇到超长文本时可以先对其中一个字符串做滑动窗口截取把大问题切成小块分别求解再合并判断这样既能控内存又能并行加速。多路并行时每个分片独立计算局部最大匹配长度最后汇总取全局最大值逻辑简单可靠。8.3 语言选型对性能的影响同一个 O(m·n) 算法用 Python 处理两个 10000 长度的字符串可能要几秒用编译型语言则只花几十毫秒。原因是 Python 解释执行和类型动态化带来的常数因子较大。如果追求极致性能可以考虑C/C数组访问零开销内存可控。JavaJIT 优化后性能非常可观字节码也能比 Python 快很多倍。Rust既有 C 的性能又通过所有权限定避免内存安全问题。调度到业务场景时如果只是工具脚本Python 完全够用如果要在服务端高频调用建议核心计算逻辑用编译型语言或加一层 C 扩展否则性能瓶颈很快会成为负担。9. 扩展到“最长公共子序列”时的关键区别9.1 为什么两个题目总被放在一起比较最长公共子序列往往被缩写为 LCS最长公共子串因为缩写也是 LCS两者名称撞车所以社区里讨论时经常混在一起。它们的核心区别我已经在前面强调过子序列允许跳过字符子串必须连续。看图对比A abcdef B abxdfe 最长公共子序列: abde (4 个字符允许跳) 最长公共子串: ab (2 个字符必须连续)这个差异直接反映在 DP 方程上题型字符不等时字符相等时最长公共子序列max(dp[i-1][j], dp[i][j-1])dp[i-1][j-1]1最长公共子串置 0dp[i-1][j-1]1两者在字符相等时的转移规则一模一样最核心的差别就是“字符不相等时如何处理”。很多人没有意识到这一点导致两个算法混着写结果必然是错误输出。9.2 实际选型建议某些场景两者会互相补充判断两个文本是否同一主题可以使用最长公共子序列长度占全文比例因为它对微小插入删除不敏感。判断两个代码文件是否连续抄袭大段代码必须使用最长公共子串长度因为内部插入空行都会使子串断裂从而降低误报率。所以了解和掌握这两个算法并不是重复造轮子而是针对不同场景准备不同的武器。10. 实测记录一组随机样例的长度与性能观察我用 Python 做了个小实验生成了不同规模的随机字符串对比多种解法的表现样例1: m500, n500 耗时: 二维DP 约 0.08s / 滚动数组 约 0.06s / 暴力法 约 0.65s 样例2: m1000, n1000 耗时: 二维DP 约 0.32s / 滚动数组 约 0.28s / 暴力法 约 5.9s 样例3: m5000, n5000 耗时: 二维DP 约 8.1s / 滚动数组 约 7.6s / 暴力法 未测(太慢)从数据上可以清楚看到暴力法在长度超过 1000 后就几乎不可用二维 DP 和滚动数组的差距没有数量级那么大但滚动数组的内存优势在更大的长度下会越来越明显。我还试过一个极端场景m20000, n20000二维 DP 需要约 4 亿格子内存直接飙到 1.6GB 以上几乎直接把进程拖垮滚动数组则只占 20001 个 int内存几十 KB运行耗时也稳定在几十秒内。由此可见生产环境优先使用滚动数组不只是礼貌性优化而是保命级别的要求。11. 最后留几个自己常用的小技巧第一个技巧写 DP 表的时候故意多用几个不同的随机样例去验证尤其是包含相同前缀、完全相等、全不相等、空字符串这些极端情形。这种用例能一次性覆盖绝大多数边界问题。第二个技巧在代码里临时加一行print(dp)人肉观察表的变化特别适合在初学阶段排查状态转移写错的问题。等逻辑稳定了再删掉调试输出回归到干净版本。第三个技巧如果最终结果只需要长度就别把dp数组暴露在函数外面把它封装成局部变量。这样既能防止意外修改状态也方便后续改成滚动数组版本时不动函数签名。第四个技巧遇到“连续片段”相关题目时先想清楚“以当前位置结尾”的状态词再用这个状态描述去推转移方程。这招比死记硬背哪道题用什么方程要可靠得多因为题目千变万化状态描述才是那个不变的内核。对我来说最长公共子串长度不仅是一个算法题更是一种思维训练它教会我如何识别“连续性约束”、如何用一维数组压状态、如何在工程里设定阈值过滤噪声。希望这篇内容能帮你在面试和日常开发中都少踩几个坑。