给定字符串a和b,输出a和b中的最长公共子串 python

题目描述：

给定两个字符串a和b，求它们的最长公共子串。

解题思路：

最长公共子串问题是求两个字符串中最长的相同子串，可以使用动态规划来解决。

我们定义一个二维数组dp[i][j]表示以a[i]和b[j]为结尾的最长公共子串的长度。即，如果a[i]和b[j]相等，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0。

接下来，我们遍历整个数组，并记录下最大的dp[i][j]的值，以及对应的结束位置。

代码实现：

def get_lcs(a, b):
len_a = len(a)
len_b = len(b)

dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]

max_len = 0
end_pos = 0

for i in range(1, len_a+1):
for j in range(1, len_b+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

return a[end_pos-max_len:end_pos]

测试样例：

a = 'abcdefg'
b = 'cdefghijk'

print(get_lcs(a, b)) # cdefg

参考资料：

https://blog.csdn.net/mrenglish233/article/details/104587952