最大公共子串算法：从暴力枚举到动态规划优化

1. 从一道经典题说起最大子串到底在求什么“求两个字符串中最大子串及最大子序列”这个标题乍一看像是算法课作业但真正动手写过的人都知道这里面藏着两个完全不同的问题。子串Substring和子序列Subsequence虽然只差一个字解法、复杂度、适用场景却天差地别。这篇先聊子串篇把最大公共子串这件事从头到尾拆干净。先说清楚定义。最大公共子串指的是两个字符串中连续出现的最长相同部分。比如abcdefg和xyzabcde它们的最大公共子串是abcde因为这五个字符在两个串里都是连续挨着的。注意“连续”这个约束是子串问题的灵魂一旦去掉连续性要求问题就退化成子序列那是另一套解法。这个问题能做什么最直接的场景是文本相似度比对。比如两份代码文件你想知道它们有多少连续相同的片段用来判断是否存在抄袭或者重复逻辑。再比如DNA序列分析两条基因链中连续匹配的碱基片段往往比零散匹配更有生物学意义。还有日常的字符串纠错、版本差异对比底层都可能用到最大公共子串的计算。适合谁来参考如果你正在准备算法面试这题是动态规划的入门经典必须手推一遍。如果你在工作中遇到了字符串比对需求想找一个能直接落地的方案这篇也会给出完整的代码和优化思路。哪怕你只是好奇“两个字符串到底有多像”看完也能自己写个小工具跑起来。我见过太多人一上来就背状态转移方程结果换个问法就懵了。所以这篇不打算只丢一段代码而是把为什么这么设计、边界怎么处理、空间怎么优化、实际跑起来会遇到什么坑全部摊开讲。子串篇讲透之后子序列篇再单独展开两篇对照着看理解会更深。2. 暴力解法与动态规划两条路的选择逻辑2.1 暴力枚举为什么在面试里会被嫌弃拿到这个问题最直觉的做法是枚举第一个字符串的所有子串对每个子串去第二个字符串里找是否存在记录最长的那个。思路没错但复杂度很难看。假设两个字符串长度分别是 m 和 n第一个串的子串数量是 m(m1)/2每个子串去第二个串里做匹配最坏又要 O(n) 甚至 O(m·n)整体轻松飙到 O(m²n) 甚至更高。我实测过当两个字符串长度都到 1000 的时候暴力解法在很多语言里已经要跑好几秒了。如果长度上万基本就卡死。所以暴力法只适合用来理解问题或者字符串极短的场景。面试里如果你只写出暴力解面试官通常会追问“能不能优化”这时候就得拿出动态规划。不过暴力法也不是一无是处。它的逻辑最直观不容易写错边界在写DP之前先用暴力法跑几个小用例拿结果去验证DP的输出这是我自己常用的对拍手段。很多人DP写挂了却不知道错在哪就是因为没有一个可信的参照。2.2 动态规划的状态定义与转移方程推导动态规划的核心在于找到一个可以递推的状态。对于最大公共子串我们定义dp[i][j]表示以第一个字符串第 i 个字符结尾、以第二个字符串第 j 个字符结尾的公共子串长度。注意这里的关键词是“以……结尾”这个定义方式直接决定了转移方程长什么样。为什么这么定义因为子串要求连续如果当前两个字符相等那么以它们结尾的公共子串长度就等于以它们前一个字符结尾的公共子串长度加一。如果当前字符不相等那么以它们结尾的公共子串根本不存在长度直接归零。写成方程就是当s1[i-1] s2[j-1]时dp[i][j] dp[i-1][j-1] 1否则dp[i][j] 0这个方程非常干净但有一个容易踩的坑最大值不一定在 dp 表的右下角。因为 dp 定义的是“以当前字符结尾”的长度最长公共子串可能出现在任意位置所以我们需要在填表的过程中用一个变量持续记录出现过的最大值同时记住它对应的结束位置方便最后把子串截取出来。对比一下子序列的转移方程那边不相等的时