查找两个字符串a,b中的最长公共子串（HJ21）

查找两个字符串a,b中的最长公共子串 题解

题目描述

https://www.nowcoder.com/share/jump/5832603751775928180959

给定两个字符串 s 和 t，找出它们的最长公共子串。如果存在多个答案，输出在较短串中最先出现的那个。

输入： - 第一行：字符串 s（1 ≤ len(s) ≤ 300） - 第二行：字符串 t（1 ≤ len(t) ≤ 300）

输出：最长公共子串

示例： - 输入：

awaabb
aawbb

- 输出：aa

---

解法

问题类型：最长公共子串

思路： 1. 确保 s 是较短串（保证优先输出较短串中先出现的） 2. 枚举 s 的所有子串，检查是否在 t 中 3. 记录最长的匹配子串

代码

a = input()
b = input()

# 确保 a 是较短的字符串
if len(a) > len(b):
    a, b = b, a

res = ''

for i in range(len(a)):
    for j in range(i, len(a)):
        sub = a[i:j + 1]
        if sub in b and len(sub) > len(res):
            res = sub

print(res)

时间复杂度：O(n³)，n 为较短串长度 空间复杂度：O(1)

优化思路：可使用动态规划优化到 O(n×m)，但 n ≤ 300 时暴力法足够。