python找到两个字符串的共同子字符串
时间: 2023-10-01 16:03:14 浏览: 46
可以使用动态规划算法来解决这个问题。具体步骤如下:
1. 创建一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符结尾和以第二个字符串的第j个字符结尾的最长公共子字符串的长度。
2. 初始化dp数组的第一行和第一列为0。
3. 遍历第一个字符串和第二个字符串的每个字符,如果两个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = 0。
4. 在遍历的过程中,记录下最长的公共子字符串的长度和位置。
5. 根据最长公共子字符串的长度和位置,从两个字符串中分别截取出公共子字符串。
下面是一个示例代码:
```
def find_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
max_len, end_pos = 0, 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_len:
max_len = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
return s1[end_pos-max_len:end_pos]
```
这个函数的参数是两个字符串s1和s2,返回值是它们的最长公共子字符串。