python最长公共子串
时间: 2023-10-15 14:26:23 浏览: 62
Python中求解最长公共子串可以使用动态规划的方法。以下是一个示例代码:
```python
def longest_common_substring(str1, str2):
m = len(str1)
n = len(str2)
# 创建一个二维数组来存储公共子串的长度
dp = [[0] * (n+1) for _ in range(m+1)]
max_length = 0 # 最长公共子串的长度
end_index = 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_length:
max_length = dp[i][j]
end_index = i
start_index = end_index - max_length # 最长公共子串的起始索引
longest_common_substring = str1[start_index:end_index] # 获取最长公共子串
return longest_common_substring
# 示例用法
str1 = "abcdefg"
str2 = "defg12345"
result = longest_common_substring(str1, str2)
print(result) # 输出:defg
```
这段代码通过动态规划的方式,利用二维数组dp来记录每个位置的公共子串长度,然后找到最长的公共子串。注意,这里求得的是最长的连续公共子串,而不是最长的公共子序列。如果需要求最长的公共子序列,则需要进行一些修改。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)