首页如何设计一个函数来寻找两个字符串之间的最长公共子串？并且，请提供一个步骤说明，如何使用这个函数接收用户通过键盘输入的两个字符串，并输出它们的最大公共子串。

如何设计一个函数来寻找两个字符串之间的最长公共子串？并且，请提供一个步骤说明，如何使用这个函数接收用户通过键盘输入的两个字符串，并输出它们的最大公共子串。

时间: 2025-06-21 10:27:10 浏览: 4

设计一个寻找两个字符串之间最长公共子串的函数通常会采用动态规划的方法。这里是一个简单的步骤来创建这样一个函数： ```python def longest_common_substring(str1, str2): # 初始化一个二维数组dp，用于存储每个位置的最长公共前缀长度 dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)] # 记录最长公共子串的长度和结束位置 max_length = 0 end_index = 0 # 遍历两个字符串 for i in range(1, len(str1) + 1): for j in range(1, len(str2) + 1): if str1[i - 1] == str2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > max_length: max_length = dp[i][j] end_index = i else: dp[i][j] = 0 # 根据end_index找到最长公共子串并返回 return str1[end_index - max_length:end_index] # 用户输入部分 str1_user_input = input("请输入第一个字符串：") str2_user_input = input("请输入第二个字符串：") result = longest_common_substring(str1_user_input, str2_user_input) print(f"这两个字符串的最长公共子串是：{result}") ``` 在这个例子中，我们首先创建一个动态规划表格`dp`来记录当前字符匹配的情况。然后遍历两个字符串，如果字符相等，则更新dp矩阵并检查是否找到了更长的子串。最后，根据最长子串的长度和结束位置，从原始字符串中提取出最长公共子串。

阅读全文