求两个字符串的最长公共子串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"

相关问题

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

可以使用动态规划来解决这个问题。

具体思路是，用一个二维数组记录两个字符串的所有子串的匹配情况，然后找到所有匹配的子串中最长的一个即可。

下面是 Python 代码实现：

def find_longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    # 构建二维数组，记录子串匹配情况
    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 str1[i - 1] == str2[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 str1[end - max_len:end]

使用该函数可以得到两个字符串的最长公共子串，例如：

str1 = "abcdefg"
str2 = "defg1234"
longest_common_substring = find_longest_common_substring(str1, str2)
print(longest_common_substring)  # 输出 "defg"

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

可以使用动态规划来解决最长公共子串的问题。

假设给出两个字符串 $s1$ 和 $s2$，用 $dp[i][j]$ 表示以 $s1$ 的第 $i$ 个字符和 $s2$ 的第 $j$ 个字符为结尾的最长公共子串的长度。

当 $s1[i] \neq s2[j]$ 时，$dp[i][j]$ 应该为 0，因为以这两个字符结尾的字符串不可能有公共子串。

当 $s1[i] = s2[j]$ 时，$dp[i][j]$ 应该为 $dp[i-1][j-1] + 1$，因为以这两个字符结尾的字符串可能有公共子串，并且公共子串的长度就是 $dp[i-1][j-1]$ 加上 1。

最终的答案就是 $dp[i][j]$ 中的最大值。

下面是该问题的 Python 代码实现：

def longest_common_substring(s1, s2):
    n1, n2 = len(s1), len(s2)
    dp = [[0] * (n2+1) for _ in range(n1+1)]
    ans = 0
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
    return ans

时间复杂度为 $O(n_1n_2)$，其中 $n_1$ 和 $n_2$ 分别是两个字符串的长度。