HJ75. 公共子串计算
题目描述
给定两个字符串，计算它们的最长公共子串的长度。
输入格式
- 第 1 行：字符串 1
- 第 2 行：字符串 2
输出格式
最长公共子串的长度（整数）。
示例
示例 1
输入：
asdfas
werasdfaswer
输出：
6
说明：
两个串的最长公共子串为 asdfas，长度为 6。
解题思路
第一步：理解问题本质
求两个字符串连续公共子串的最大长度。与 HJ65 的区别是：本题只求长度，不要求输出具体子串。
第二步：暴力解法（枚举子串）
枚举一个串的所有子串，检查是否在另一个串中出现，取最长的长度。
问题：枚举所有子串 O(n²) 且每次查找 O(m)，总复杂度 O(n²·m)，效率低。
第三步：优化解法（二维 DP）
定义 dp[i][j] 表示以 a[i-1]、b[j-1] 结尾的最长公共子串长度：
- 若
a[i-1] == b[j-1]，则dp[i][j] = dp[i-1][j-1] + 1 - 否则
dp[i][j] = 0
答案为所有 dp 的最大值，复杂度 O(n·m)。
第四步：最优解法（滚动数组）
dp[i][j] 只依赖 dp[i-1][j-1]，即上一行左一个元素。可以用一维数组滚动，只保留上一行：
dp = [0] * (m + 1)
for i in range(1, n + 1):
prev = 0 # 记录 dp[i-1][j-1]
for j in range(1, m + 1):
cur = dp[j] # 记录 dp[i-1][j]
if a[i - 1] == b[j - 1]:
dp[j] = prev + 1
best = max(best, dp[j])
else:
dp[j] = 0
prev = cur
空间降为 O(m)，时间仍为 O(n·m)。
完整代码实现
算法可视化 · 逐帧回放这道题的代码396 帧 · 录制输入
import sys
def solve() -> None:
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
n, m = len(a), len(b)
# 滚动数组，只需保留上一行
dp = [0] * (m + 1)
best = 0
for i in range(1, n + 1):
prev = 0 # dp[i-1][j-1]
for j in range(1, m + 1):
cur = dp[j] # 记录 dp[i-1][j]
if a[i - 1] == b[j - 1]:
dp[j] = prev + 1
best = max(best, dp[j])
else:
dp[j] = 0
prev = cur
print(best)
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，a = "asdfas"（n=6），b = "werasdfaswer"（m=12）。
逐行滚动计算时，记录下当前能形成的最长连续匹配。当 a 的整个子串 "asdfas" 与 b 中下标 3~8 的 "asdfas" 完全匹配时，dp 值逐字符累加为 1、2、3、4、5、6。
例如最后一步：a[5]='s' 与 b[8]='s' 相等，dp[j] = prev + 1，此时 prev 保存的正是 dp[i-1][j-1]=5，得到 6。
最终 best = 6，输出 6。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²·m) | O(1) | 子串过多，不可行 |
| 二维 DP | O(n·m) | O(n·m) | 标准 DP 表 |
| 最优（滚动） | O(n·m) | O(m) | 只用一行滚动数组 |
n、m 分别为两个字符串的长度
易错点总结
1. 混淆"子串"与"子序列"
子串必须连续，字符不匹配时应把 dp 清零，而不是继承对角线或相邻的值。
2. 滚动数组时 prev 的更新顺序
必须先保存旧的 dp[j]（即 dp[i-1][j]）为 cur，再更新 dp[j]，最后把 prev 更新为 cur。若顺序写错，dp[i-1][j-1] 会被新值污染。
3. 空串情况
两串无任何相同字符时，best 保持 0，需正确输出 0。
扩展思考
- 本题与 HJ65（输出子串）是同一算法的两种应用，前者求长度，后者求具体子串。
- 空间优化后可进一步推导滚动数组公式，这是 DP 空间优化（滚到 O(m)）的经典范例。