Python 求最长公共子串 ？

在 Python 中，可以使用动态规划（Dynamic Programming）的方法来解决最长公共子串（Longest Common Substring）的问题。以下是一个示例代码：

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)

    # 创建一个二维数组 dp，用于存储子问题的解
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0  # 最长公共子串的长度
    end = 0  # 最长公共子串在 s1 中的结束位置

    # 动态规划求解
    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

    # 提取最长公共子串
    start = end - max_len
    return s1[start:end]

# 示例
s1 = "ABCDEFG"
s2 = "XYZBCDEFG"
print(longest_common_substring(s1, s2))  # 输出：BCDEFG

这段代码首先创建了一个二维数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符之间的最长公共子串的长度。然后，使用两个嵌套的循环遍历 s1 和 s2 的所有字符，根据字符是否相等来更新 dp 数组。如果 s1[i - 1] 等于 s2[j - 1]，则 dp[i][j] 等于 dp[i - 1][j - 1] + 1，表示最长公共子串的长度加 1。同时，如果 dp[i][j] 大于当前记录的最长公共子串的长度 max_len，则更新 max_len 和 end 的值。如果 s1[i - 1] 不等于 s2[j - 1]，则 dp[i][j] 等于 0，表示当前字符不能构成更长的公共子串。最后，根据 max_len 和 end 的值，提取出最长公共子串并返回。