最长公共子串算法详解：从暴力枚举到动态规划与滚动数组优化

1. 从一道面试题说起：为什么"最大子串"值得单独拎出来讲

很多人第一次接触"求两个字符串中最大子串"这个问题，是在准备技术面试的时候。题目描述很简洁：给定两个字符串，找出它们之间最长的公共连续子串。看起来不难，但真正动手写的时候，各种边界情况会把你折磨得够呛。

我自己最早遇到这个问题，是在做一个文本比对工具的时候。当时的需求是：用户上传两段文本，系统要自动标出它们之间最长的连续重复片段，用来判断是否存在抄袭或者内容复用。一开始我觉得这还不简单，暴力枚举就行了。结果第一版代码跑一个几千字的文本，直接卡死。后来才意识到，暴力解法的时间复杂度是O(n³)，两个长度为n的字符串，运算量直接爆炸。

这就是为什么"最大子串"值得单独拿出来讲。它表面上是一个算法题，实际上涉及的是连续性的约束——子串要求字符必须挨在一起，不能跳过任何位置。这个约束看似简单，却让问题的解法跟"最大子序列"走上了完全不同的路。子序列可以跳着选，用动态规划很自然；子串必须连续，就需要考虑以某个位置结尾的最优解是什么。

这篇文章我会把"最大子串"这个问题彻底拆开，从暴力解法讲到动态规划，再讲到滚动数组优化，最后给出完整的代码实现和实测数据。不管你是刚学算法的新手，还是想复习一下动态规划的老手，应该都能从中找到有用的东西。关键词就三个：最长公共子串、动态规划、滚动数组优化，全文围绕它们展开。

2. 暴力枚举的完整实现与性能天花板

2.1 暴力解法的思路拆解

暴力解法的逻辑非常直白：枚举字符串A的所有子串，再枚举字符串B的所有子串，两两比较，找出最长的那个公共子串。

具体来说，对于字符串A，我们用两层循环确定子串的起点和终点，得到A的所有子串。对于每一个A的子串，再用两层循环去B里面找是否存在相同的子串。如果存在，就更新最大长度。

这个思路写起来大概是这样：

def longest_common_substring_brute(s1, s2): max_len = 0 result = "" for i in range(len(s1)): for j in range(i + 1, len(s1) + 1): sub = s1[i:j] if sub in s2 and len(sub) > max_len: max_len = len(sub) result = sub return result

这段代码看起来简洁，但问题在于sub in s2这个操作本身就需要O(n)的时间。外层两层循环是O(n²)，内层查找是O(n)，合起来就是O(n³)。如果两个字符串长度都是1000，运算量大约是10亿次，在普通机器上跑几秒钟都出不来结果。

2.2 暴力解法到底慢在哪里

我实测过一组数据，用上面这段代码跑不同长度的字符串，结果如下：

可以看到，长度从500增加到1000，耗时翻了8倍。这完全符合O(n³)的增长曲线。在实际工程中，如果文本长度超过几百，暴力解法就完全不可用了。

但暴力解法也不是一无是处。它的优点是逻辑简单、不容易写错，在字符串很短（比如长度小于50）的场景下，反而比动态规划更省事。而且暴力解法不需要额外的内存空间，空间复杂度是O(1)。所以如果你只是写个脚本处理几十个字符的短字符串，暴力解法完全够用。

注意：很多教程一上来就说"暴力解法不可取"，但实际工作中，如果数据规模很小，简单直接的方案往往比复杂的最优解更靠谱。关键是要知道你的数据规模有多大。

2.3 暴力解法的两个常见优化

虽然暴力解法整体复杂度降不下来，但有两个小优化可以让它快不少。

第一个优化是从长到短枚举。与其枚举所有子串再找最长的，不如先枚举最长的可能长度，一旦找到就立即返回。这样在最好情况下（两个字符串完全相同），第一次就能找到答案，复杂度降到O(n)。

def longest_common_substring_brute_v2(s1, s2): for length in range(len(s1), 0, -1): for i in range(len(s1) - length + 1): sub = s1[i:i+length] if sub in s2: return sub return ""

第二个优化是用集合加速查找。把字符串B的所有子串提前存到一个集合里，查找操作就从O(n)降到O(1)。但预处理本身需要O(n²)的时间，所以整体复杂度还是O(n³)，只是常数项小了很多。

这两个优化在实际中都有用，但都改变不了暴力解法的本质瓶颈。要真正解决问题，必须换思路。

3. 动态规划解法的推导过程与状态定义

3.1 为什么动态规划适合这个问题

暴力解法的问题在于重复计算。比如比较A[0:5]和B[0:5]是否相等，和比较A[0:6]和B[0:6]是否相等，前面的字符其实已经比较过了，但暴力解法会重新比一遍。

动态规划的核心思想就是把中间结果存下来，避免重复计算。对于最大子串问题，我们可以定义一个二维数组dp[i][j]，表示以A的第i个字符和B的第j个字符结尾的最长公共子串长度。

注意这里的"结尾"两个字非常关键。子串必须连续，所以如果我们知道了以A[i]和B[j]结尾的最长公共子串长度，那么以A[i+1]和B[j+1]结尾的最长公共子串长度就可以直接推导出来。

3.2 状态转移方程的推导

状态转移方程的逻辑是这样的：

• 如果A[i] == B[j]，那么以它们结尾的公共子串长度，等于以A[i-1]和B[j-1]结尾的公共子串长度加1。
• 如果A[i] != B[j]，那么以它们结尾的公共子串不存在，长度为0。

用数学公式表达就是：

dp[i][j] = dp[i-1][j-1] + 1, 如果 A[i] == B[j] dp[i][j] = 0, 如果 A[i] != B[j]

这个方程看起来简单，但它是整个动态规划解法的核心。我刚开始学的时候，总是想不通为什么不相等的时侯要置0而不是取最大值。后来才明白：因为子串要求连续，一旦当前字符不匹配，以这个位置结尾的公共子串就断了，长度只能是0。而全局的最大值，是在填表的过程中用一个变量单独记录的。

3.3 完整代码实现与逐行注释

def longest_common_substring_dp(s1, s2): m, n = len(s1), len(s2) # dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串长度 dp = [[0] * (n + 1) for _ in range(m + 1)] max_len = 0 end_pos = 0 # 记录最长公共子串在 s1 中的结束位置 for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 if dp[i][j] > max_len: max_len = dp[i][j] end_pos = i # 不相等时 dp[i][j] 保持为 0 return s1[end_pos - max_len: end_pos]

这段代码的时间复杂度是O(m×n)，空间复杂度也是O(m×n)。相比暴力解法的O(n³)，已经是一个巨大的飞跃。对于长度1000的字符串，动态规划只需要100万次运算，耗时大约0.1秒，比暴力解法快了100多倍。

3.4 填表过程的直观理解

我用一个具体例子来演示填表过程。假设s1 = "abcde"，s2 = "abfde"，我们来看dp表是怎么填的。

从表中可以看到，最大值是2，对应的是"ab"和"de"两个公共子串。如果我们要找的是第一个出现的最长公共子串，那就是"ab"；如果要找最后一个，那就是"de"。代码中我们用end_pos记录的是最后一次更新最大值的位置，所以返回的是"de"。

这个填表过程有一个很直观的几何意义：dp[i][j]的值，等于从(i,j)位置向左上角看，能连续匹配多少个字符。你可以把两个字符串分别放在行和列上，匹配的字符就是对角线上的连续段，最长的对角线就是答案。

4. 滚动数组优化：把空间从O(n²)降到O(n)

4.1 为什么可以优化空间

观察状态转移方程dp[i][j] = dp[i-1][j-1] + 1，你会发现一个关键点：dp[i][j]只依赖于dp[i-1][j-1]，也就是左上角的值。它不依赖于同一行的其他值，也不依赖于同一列的其他值。

这意味着我们不需要保存整个二维数组，只需要保存上一行的数据就够了。在计算第i行的时候，第i-2行及更早的数据已经完全用不到了。

这个优化思路叫做滚动数组，是动态规划中非常常用的一种空间优化技巧。它的本质是：既然只需要前一行的数据，那就只开两行数组，交替使用。

4.2 一维数组的实现细节

进一步观察，我们甚至可以用一个一维数组来实现。关键在于从右往左遍历。

为什么？因为dp[j]在更新前存的是上一行的值（dp[i-1][j]），更新后存的是当前行的值（dp[i][j]）。而dp[i][j]需要用到dp[i-1][j-1]，也就是更新前的dp[j-1]。如果我们从左往右遍历，dp[j-1]已经被更新成当前行的值了，就会出错。从右往左遍历，dp[j-1]还是上一行的值，正好可以用。

def longest_common_substring_rolling(s1, s2): m, n = len(s1), len(s2) dp = [0] * (n + 1) max_len = 0 end_pos = 0 for i in range(1, m + 1): # 从右往左遍历，保证 dp[j-1] 还是上一行的值 for j in range(n, 0, -1): if s1[i-1] == s2[j-1]: dp[j] = dp[j-1] + 1 if dp[j] > max_len: max_len = dp[j] end_pos = i else: dp[j] = 0 # 注意这里必须置0 return s1[end_pos - max_len: end_pos]

这段代码的空间复杂度从O(m×n)降到了O(n)。对于长度1000的字符串，二维数组需要100万个整数，大约8MB内存；一维数组只需要1000个整数，大约8KB。差距是1000倍。

4.3 滚动数组的常见坑

滚动数组写起来简单，但有两个坑特别容易踩。

第一个坑是忘记置0。在二维数组中，dp[i][j]不相等时默认就是0，因为数组初始化就是0。但在一维数组中，dp[j]可能还保留着上一轮的值，如果不相等时必须显式置0，否则会得到错误的结果。

第二个坑是遍历方向搞反。前面说了必须从右往左，但很多人习惯性地从左往右写，结果就是答案偏大。这个bug很隐蔽，因为小数据量下可能碰巧得到正确结果，只有数据量大了才会暴露。

提示：如果你不确定滚动数组写得对不对，可以先用二维数组版本跑一遍，再用滚动数组版本跑同样的输入，对比结果是否一致。这是最可靠的验证方法。

4.4 三种解法的性能对比

我用长度1000的随机字符串做了一组对比测试：

可以看到，二维DP和滚动数组在时间上几乎没差别，但空间占用差了1000倍。在实际工程中，如果字符串很长，滚动数组是更好的选择。

5. 实际工程中的边界情况与踩坑记录

5.1 空字符串和单字符的处理

理论上的算法和实际代码之间，往往隔着一堆边界情况。最大子串问题最常见的边界情况包括：

• 两个字符串都为空：应该返回空字符串。
• 一个为空一个不为空：也应该返回空字符串。
• 两个字符串完全相同：应该返回整个字符串。
• 两个字符串完全没有公共字符：应该返回空字符串。

这些情况在算法描述中通常不会提到，但写代码时必须处理。我的习惯是在函数开头加一个快速判断：

if not s1 or not s2: return ""

这一行代码能避免后面所有的索引越界问题。

5.2 多个最长子串时返回哪一个

如果两个字符串有多个长度相同的最长公共子串，应该返回哪一个？这个问题在算法题中通常不会明确说明，但在实际工程中很重要。

比如s1 = "abcde"，s2 = "abfde"，最长公共子串有"ab"和"de"两个，长度都是2。上面的代码返回的是"de"，因为它是最后被更新的。如果你希望返回第一个出现的，就需要把更新条件改成>而不是>=，并且在第一次达到最大值时就记录下来。

我在做文本比对工具的时候，就遇到过这个问题。用户期望看到的是第一个最长公共子串，而不是最后一个。后来我把代码改成了记录所有达到最大长度的子串，最后根据业务需求选择。

5.3 大小写敏感与Unicode字符

另一个容易忽略的问题是大小写敏感。在英文文本中，"Hello"和"hello"是否算匹配？这取决于业务需求。如果要做大小写不敏感的匹配，可以在比较之前统一转成小写。

Unicode字符是另一个坑。Python的字符串索引是按字符来的，不是按字节。所以对于中文、日文等多字节字符，s1[i]取到的是一个完整的字符，不会出现半个字符的情况。但如果你用C++或Java，就要注意字符编码的问题。

5.4 实际项目中的性能调优记录

我在一个文本比对项目中，最初用的是二维DP，处理一篇5000字的文章需要大约3秒。后来改成滚动数组，时间降到2.8秒，提升不明显，因为瓶颈在O(n²)的时间复杂度上，空间优化不影响时间。

真正让性能大幅提升的，是先用哈希做快速筛选。具体做法是：先把两个字符串切成固定长度的块（比如长度为10），用哈希表记录每个块出现的位置。只有当两个字符串存在相同的块时，才在这个块附近做精细的最大子串匹配。这个优化把平均耗时从2.8秒降到了0.3秒，因为大部分文本块根本不匹配，直接跳过了。

这个经验告诉我：算法优化不一定要死磕时间复杂度，有时候从业务层面做剪枝，效果更好。

6. 从子串到子序列：两个问题的本质区别

6.1 连续性约束带来的解法差异

讲完最大子串，有必要简单提一下最大子序列，因为很多人会把这两个问题搞混。

最大子串要求字符连续，最大子序列允许字符不连续。这个区别看似微小，却导致解法完全不同。

对于最大子序列，状态转移方程是：

dp[i][j] = dp[i-1][j-1] + 1, 如果 A[i] == B[j] dp[i][j] = max(dp[i-1][j], dp[i][j-1]), 如果 A[i] != B[j]

注意不相等时的处理：子串直接置0，子序列则取左边和上边的最大值。这是因为子序列可以跳过当前字符，继续用之前的匹配结果。

6.2 一个例子看清两者的区别

假设s1 = "abcde"，s2 = "ace"。

• 最长公共子串是"a"或"c"或"e"，长度为1。
• 最长公共子序列是"ace"，长度为3。

这个例子很直观地展示了连续和不连续的区别。子序列可以跳过"b"和"d"，直接匹配"a"、"c"、"e"。

6.3 子串问题的独特价值

虽然子序列的解法更通用，但子串问题在实际中也有不可替代的价值。比如：

• 抄袭检测：连续的大段文字重复，比零散的关键词重复更能说明问题。
• DNA序列比对：连续的基因片段匹配，比零散的碱基匹配更有生物学意义。
• 代码相似度检测：连续的代码块重复，比零散的函数名重复更能说明代码复用。

所以子串和子序列不是谁替代谁的关系，而是针对不同场景的不同工具。理解它们的区别，才能在合适的场景选择合适的方法。

7. 完整代码与测试用例

7.1 最终版本的完整实现

把前面的优化和边界处理整合起来，最终版本如下：

def longest_common_substring(s1, s2): """ 求两个字符串的最长公共子串 返回第一个出现的最长公共子串 """ if not s1 or not s2: return "" m, n = len(s1), len(s2) dp = [0] * (n + 1) max_len = 0 end_pos = 0 for i in range(1, m + 1): for j in range(n, 0, -1): if s1[i-1] == s2[j-1]: dp[j] = dp[j-1] + 1 if dp[j] > max_len: max_len = dp[j] end_pos = i else: dp[j] = 0 return s1[end_pos - max_len: end_pos]

7.2 覆盖各种情况的测试用例

# 普通情况 assert longest_common_substring("abcde", "abfde") == "ab" # 完全相同 assert longest_common_substring("hello", "hello") == "hello" # 完全不同 assert longest_common_substring("abc", "def") == "" # 空字符串 assert longest_common_substring("", "abc") == "" assert longest_common_substring("abc", "") == "" # 单字符 assert longest_common_substring("a", "a") == "a" # 包含关系 assert longest_common_substring("abc", "xabcy") == "abc" # 多个相同长度的子串 result = longest_common_substring("abcde", "abfde") assert result in ["ab", "de"]

这些测试用例覆盖了绝大多数边界情况。每次修改代码后跑一遍，能避免大部分低级错误。

7.3 性能测试的参考数据

最后附上一组性能测试数据，供你参考：

从数据可以看出，动态规划在长度超过200之后优势非常明显。而滚动数组相比二维DP，时间上略有优势（因为内存访问更局部化），空间上优势巨大。

我在实际项目中的体会是：如果字符串长度不超过100，怎么写都行；如果超过500，必须用动态规划；如果超过5000，还需要考虑分块哈希等更高级的优化手段。算法选择没有银弹，关键是根据数据规模选合适的工具。