输入两个字符串A,B,输出A和B中的最长公共子串
时间: 2023-12-20 12:12:06 浏览: 70
好的,可以使用动态规划算法来解决这个问题。
首先定义一个二维数组dp,其中dp[i][j]表示以A[i-1]和B[j-1]结尾的最长公共子串长度。如果A[i-1]和B[j-1]不相等,则dp[i][j]=0,否则dp[i][j]=dp[i-1][j-1]+1。
然后遍历dp数组,找到最长的公共子串长度以及对应的起始位置。
最长公共子串的长度就是dp数组中的最大值,对应的起始位置可以通过记录最大值时的i和j来确定。
最后,根据最长公共子串的长度和起始位置,可以从A中截取出最长公共子串并返回。
下面是具体的实现代码:
```
def longest_common_substring(A, B):
m, n = len(A), len(B)
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 A[i-1] == B[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 A[end_pos-max_len:end_pos]
```
在这个代码中,我们使用了两个变量max_len和end_pos来记录最长公共子串的长度和起始位置。在遍历dp数组的过程中,如果dp[i][j]比max_len要大,就更新max_len和end_pos的值。
最后,返回从A中截取出来的最长公共子串即可。
相关推荐
![](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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)