Python 求两个字符串的最长公共子串
Python3 实例最长公共子串问题是指给定两个字符串，找到它们之间最长的公共子串。子串是指字符串中连续的字符序列。我们可以使用动态规划的方法来解决这个问题。
实例
def longest_common_substring(s1, s2):
m = len(s1)
n = len(s2)
# 创建一个二维数组来存储最长公共子串的长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # 记录最长公共子串的长度
end_pos = 0 # 记录最长公共子串的结束位置
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
# 返回最长公共子串
return s1[end_pos - max_length:end_pos]
# 测试
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("最长公共子串是:", result)
m = len(s1)
n = len(s2)
# 创建一个二维数组来存储最长公共子串的长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # 记录最长公共子串的长度
end_pos = 0 # 记录最长公共子串的结束位置
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
# 返回最长公共子串
return s1[end_pos - max_length:end_pos]
# 测试
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("最长公共子串是:", result)
代码解析：
dp是一个二维数组，dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子串的长度。- 我们遍历两个字符串的每个字符，如果
s1[i-1]和s2[j-1]相等，则dp[i][j]的值等于dp[i-1][j-1] + 1，否则dp[i][j]为 0。 max_length用于记录最长公共子串的长度，end_pos用于记录最长公共子串的结束位置。- 最后，我们通过
s1[end_pos - max_length:end_pos]来获取最长公共子串。
输出结果：
最长公共子串是: bcd
点我分享笔记