python 最长公共子串

最长公共子串问题是指在两个或多个字符串中找到一个最长的子串，使得这个子串在所有字符串中都出现过。下面是 Python 的一种实现方式：

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    # 初始化一个二维数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 记录最长公共子串的长度和结束位置
    max_len = 0
    end_pos = 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_pos = i
            else:
                dp[i][j] = 0
    return str1[end_pos - max_len:end_pos]

该函数接受两个字符串作为参数，使用动态规划的思想，初始化一个二维数组 dp，其中 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 结尾的最长公共子串的长度。最长公共子串的长度和结束位置分别记录在 max_len 和 end_pos 中。最后返回最长公共子串。