帮我写段代码,最长公共子串匹配
时间: 2023-08-06 11:12:10 浏览: 85
当然可以,以下是一种求解最长公共子串的动态规划解法:
```python
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
res = 0 # 最长公共子串的长度
end = 0 # 最长公共子串在 s1 中的结尾位置
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] > res:
res = dp[i][j]
end = i
else:
dp[i][j] = 0
return s1[end - res: end]
```
其中,`dp[i][j]` 表示以 `s1[i-1]` 和 `s2[j-1]` 结尾的最长公共子串的长度。如果 `s1[i-1] == s2[j-1]`,则 `dp[i][j]` 可以由 `dp[i-1][j-1]` 转移得到;否则,`dp[i][j]` 必须为 0。
最终,最长公共子串的长度为 `res`,结尾位置为 `end`,因此可以通过 `s1[end - res: end]` 得到最长公共子串。
阅读全文