python求两个字符串的最长公共子串
时间: 2023-08-10 14:07:12 浏览: 57
C语言求两个字符串的最长公共子串
5星 · 资源好评率100%
可以使用动态规划来解决这个问题。
具体思路是,用一个二维数组记录两个字符串的所有子串的匹配情况,然后找到所有匹配的子串中最长的一个即可。
下面是 Python 代码实现:
```
def find_longest_common_substring(str1, str2):
m = len(str1)
n = len(str2)
# 构建二维数组,记录子串匹配情况
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
end = 0
# 遍历两个字符串,记录匹配情况
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end = i
else:
dp[i][j] = 0
# 返回最长公共子串
return str1[end - max_len:end]
```
使用该函数可以得到两个字符串的最长公共子串,例如:
```
str1 = "abcdefg"
str2 = "defg1234"
longest_common_substring = find_longest_common_substring(str1, str2)
print(longest_common_substring) # 输出 "defg"
```
阅读全文