查找两个字符串中的最大公共子串
时间: 2023-05-20 19:01:02 浏览: 95
可以使用动态规划来解决这个问题。假设有两个字符串S1和S2,我们定义一个二维数组dp,其中dp[i][j]表示S1以第i个字符结尾的子串和S2以第j个字符结尾的子串的最长公共子串的长度。则有以下状态转移方程:
dp[i][j] = dp[i-1][j-1] + 1, if S1[i] == S2[j]
dp[i][j] = 0, if S1[i] != S2[j]
其中,如果S1[i]等于S2[j],则说明当前字符可以加入到最长公共子串中,所以dp[i][j]等于dp[i-1][j-1]加上1;如果S1[i]不等于S2[j],则说明当前字符不能加入到最长公共子串中,所以dp[i][j]等于0。
最终的最长公共子串的长度就是dp数组中的最大值。如果需要输出最长公共子串本身,可以记录dp数组中最大值的位置,然后从该位置开始向左或向上遍历dp数组,直到遇到0为止,这样就可以得到最长公共子串了。
以下是代码示例:
def find_lcs(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 = "abcdefg"
s2 = "bcdefgh"
print(find_lcs(s1, s2)) # 输出 "bcdef"
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)