最长公共子串python

最长公共子串可以使用动态规划来解决。具体实现如下：

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end = 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 = i
            else:
                dp[i][j] = 0
    return s1[end - max_len:end]

s1 = "abcdefg"
s2 = "defghijk"
print(longest_common_substring(s1, s2)) # 输出 "def"

相关问题

求两个字符串的最长公共子串python

可以使用动态规划算法来求解两个字符串的最长公共子串，以下是Python实现示例：

def find_longest_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 - 1
            else:
                dp[i][j] = 0
    return s1[end_pos-max_len+1:end_pos+1]

使用示例：

s1 = "abcdefg"
s2 = "bcdefgh"
print(find_longest_common_substring(s1, s2)) # 输出 "bcdef"

给定字符串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