HJ65. 查找两个字符串a,b中的最长公共子串
题目描述
给定两个字符串 a 和 b，找出它们的最长公共子串。若存在多个答案，输出在较短串中最先出现的那个。
输入格式
- 第 1 行：字符串 a（小写字母）
- 第 2 行：字符串 b（小写字母）
输出格式
最长公共子串；若有多个，输出较短串中最先出现的那个。
示例
示例 1
输入：
awaabb
aawbb
输出：
aa
说明：
两个串的最长公共子串为 aa（较短串 awaabb 中最先出现的连续 aa 在下标 2、3）。
示例 2
输入：
abcdefghijklmnop
abcsafjklmnopqrstuvw
输出：
jklmnop
说明：
两个串的最长公共子串为 jklmnop，长度为 7。
解题思路
第一步：理解问题本质
要求的是连续的公共子串（不是可以不连续的公共子序列）。公共子串比公共子序列简单，因为子串必须连续，匹配一旦断裂就重新开始计数。
第二步：暴力解法（枚举所有子串）
枚举 a 的所有子串，逐个检查它是否是 b 的子串，记录最长的那个。
问题：枚举所有子串需要 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 + 记录最短串位置）
本题要求"较短串中最先出现"的答案。做法是把较短串作为 a，按 i 递增遍历。当 dp[i][j] 严格大于当前最大值时才更新记录，这样即使有多个等长的最优子串，也只会记录第一次（在较短串中下标最小）出现的那个。
if dp[i][j] > best: # 仅严格大于才更新，保留"最先出现"
best = dp[i][j]
end = i # 在较短串 a 中的结束下标
print(a[end - best:end])
由于遍历 i 是从小到大，严格大于条件保证相同长度的子串取到的是最先出现的那个。
完整代码实现
算法可视化 · 逐帧回放这道题的代码120 帧 · 录制输入
import sys
def solve() -> None:
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
# 让 a 为较短串，保证"较短串中最先出现"
if len(a) > len(b):
a, b = b, a
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
best = 0
end = 0 # 在较短串 a 中的结束下标（开区间）
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > best: # 仅严格大于才更新，保留"最先出现"
best = dp[i][j]
end = i
else:
dp[i][j] = 0
print(a[end - best:end])
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，较短串 a = "awaabb"，较长串 b = "aawbb"。
逐对字符比较，dp 表中值为 2 的位置代表长度为 2 的公共子串：
a[1]='w'与b[1]='a'不等，dp=0a[2]='a'与b[2]='w'不等，dp=0a[2]='a'与b[1]='a'相等，dp[2][1]=dp[1][0]+1=1a[3]='a'与b[1]='a'相等，dp[3][1]=dp[2][0]+1=1；a[3]='a'与b[2]='a'相等，dp[3][2]=dp[2][1]+1=2
当 dp[3][2]=2 时，best 从 1 更新为 2，end=3。
之后继续遍历，没有出现长度大于 2 的子串。最终 best=2，end=3，输出 a[3-2:3] = a[1:3] = "aa"，结果正确。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²·m) | O(1) | 子串过多，不可行 |
| 二维 DP | O(n·m) | O(n·m) | 标准 DP 表 |
| 最优（滚动） | O(n·m) | O(m) | 可只用一行滚动数组 |
n、m 分别为两个字符串的长度
易错点总结
1. 混淆"子串"与"子序列"
子串必须连续，匹配断裂要清零重新计数；子序列才允许跳过字符。
2. 未保证"较短串中最先出现"
若不把较短串放在 a 并配合"仅严格大于才更新"的逻辑，多解时可能输出非首次出现的子串。
3. 更新条件用了 >=
若用 >=，相同长度的子串会把 end 更新为较靠后的位置，导致输出错误。必须用 >。
扩展思考
- 空间可以进一步优化：
dp[i]只依赖dp[i-1]，可用滚动数组把空间降到 O(m)。 - 求最长公共子序列（允许不连续）只需把转移改为"不等时取上方或左方最大值"，问题本质不同。