企业官网建设流程全解析

1. 从一道经典题说起：最大子串到底在求什么

“求两个字符串中最大子串及最大子序列”这个标题，乍一看像是算法课作业，但真正动手写过的人都知道，这里面藏着两个完全不同的问题。子串（Substring）和子序列（Subsequence）虽然只差一个字，解法、复杂度、适用场景却天差地别。这篇先聊子串篇，把最大公共子串这件事从头到尾拆干净。

先说清楚定义。最大公共子串指的是两个字符串中连续出现的最长相同部分。比如"abcdefg"和"xyzabcde"，它们的最大公共子串是"abcde"，因为这五个字符在两个串里都是连续挨着的。注意“连续”这个约束是子串问题的灵魂，一旦去掉连续性要求，问题就退化成子序列，那是另一套解法。

这个问题能做什么？最直接的场景是文本相似度比对。比如两份代码文件，你想知道它们有多少连续相同的片段，用来判断是否存在抄袭或者重复逻辑。再比如DNA序列分析，两条基因链中连续匹配的碱基片段，往往比零散匹配更有生物学意义。还有日常的字符串纠错、版本差异对比，底层都可能用到最大公共子串的计算。

适合谁来参考？如果你正在准备算法面试，这题是动态规划的入门经典，必须手推一遍。如果你在工作中遇到了字符串比对需求，想找一个能直接落地的方案，这篇也会给出完整的代码和优化思路。哪怕你只是好奇“两个字符串到底有多像”，看完也能自己写个小工具跑起来。

我见过太多人一上来就背状态转移方程，结果换个问法就懵了。所以这篇不打算只丢一段代码，而是把为什么这么设计、边界怎么处理、空间怎么优化、实际跑起来会遇到什么坑全部摊开讲。子串篇讲透之后，子序列篇再单独展开，两篇对照着看，理解会更深。

2. 暴力解法与动态规划：两条路的选择逻辑

2.1 暴力枚举为什么在面试里会被嫌弃

拿到这个问题，最直觉的做法是：枚举第一个字符串的所有子串，对每个子串去第二个字符串里找是否存在，记录最长的那个。思路没错，但复杂度很难看。假设两个字符串长度分别是 m 和 n，第一个串的子串数量是 m(m+1)/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 定义的是“以当前字符结尾”的长度，最长公共子串可能出现在任意位置，所以我们需要在填表的过程中用一个变量持续记录出现过的最大值，同时记住它对应的结束位置，方便最后把子串截取出来。

对比一下子序列的转移方程，那边不相等的时