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

本节目标：理解“HJ65 查找两个字符串a,b中的最长公共子串”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：32.72% 时间限制：1秒 空间限制：32M 知识点==字符串== 描述 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！ 数据范围：字符串长度1≤�����ℎ≤300 1≤length≤300 进阶：时间复杂度：�(�3) O(_n_3) ，空间复杂度：�(�) O(n) 输入描述： 输入两个字符串 输出描述： 返回重复出现的字符 示例1 输入： abcdefghijklmnopabcsafjklmnopqrstuvw ==复制== 输出： jklmnop

为了查找两个字符串中的最长公共子串，我们可以使用动态规划的方法。具体算法如下：

1. 创建一个二维数组 dp，其中 dp[i][j] 表示以 a[i-1] 和 b[j-1] 结尾的最长公共子串的长度。这里，a[i-1] 表示字符串 a 的第 i 个字符，b[j-1] 表示字符串 b 的第 j 个字符。

2. 初始化这个二维数组的所有元素为0。

3. 遍历两个字符串的所有字符，使用双层循环。

4. 在每次循环中，如果找到匹配的字符对 a[i] == b[j]，则 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = 0。

5. 同时记录最长公共子串的长度和位置。

6. 根据记录的位置和长度，截取并输出最长公共子串。

以下是对应的Python代码实现：

定义一个函数，用于找到两个字符串中的最长公共子串

def find_longest_common_substring(a, b):

如果a比b长，交换它们，确保a是较短的字符串

if len(a) > len(b): a, b = b, a

获取a和b的长度

len_a, len_b = len(a), len(b)

初始化动态规划表格，用于记录子串长度

dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]

初始化最长公共子串的长度和在a中的结束位置

max_length = 0 end_index_in_a = 0

遍历字符串a和b的每个字符

for i in range(1, len_a + 1): for j in range(1, len_b + 1):

如果当前字符匹配

if a[i-1] == b[j-1]:

更新dp表格的当前位置为左上角位置的值加1

dp[i][j] = dp[i-1][j-1] + 1

如果当前公共子串的长度大于已知的最长长度

if dp[i][j] > max_length:

更新最长长度和结束位置

max_length = dp[i][j] end_index_in_a = i

如果当前字符不匹配，重置当前位置的值为0

else: dp[i][j] = 0

根据最长公共子串的长度和结束位置，从a中截取并返回最长公共子串

return a[end_index_in_a - max_length:end_index_in_a]

从标准输入读取两个字符串

str1 = input() str2 = input()

调用函数并打印输出最长公共子串

print(find_longest_common_substring(str1, str2)) 此代码将输出在较短串中最先出现的最长公共子串。例如，输入 "abcdefghijklmnop" 和 "abcsafjklmnopqrstuvw" 将会输出 "jklmnop"。这段代码的时间复杂度是O(n^2)，其中n是字符串的长度，空间复杂度是O(n^2)，用于存储动态规划表。如果你想要一个时间复杂度更低的算法，可以考虑使用后缀数组或者后缀树等更高级的数据结构。