最长公共子串python代码实现

最长公共子串（Longest Common Substring, LCS）问题是指在两个或多个字符串中找到最长的连续字符序列，这个序列在所有给定的字符串中都存在。以下是使用Python实现最长公共子串问题的代码示例。

def longest_common_substring(str1, str2):
    m, n = len(str1), len(str2)
    counter = [[0] * (n + 1) for _ in range(m + 1)]
    longest, x_longest = 0, 0

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                counter[i][j] = 0
            elif str1[i - 1] == str2[j - 1]:
                counter[i][j] = counter[i - 1][j - 1] + 1
                if counter[i][j] > longest:
                    longest = counter[i][j]
                    x_longest = i
            else:
                counter[i][j] = 0

    lcs = str1[x_longest - longest: x_longest]
    return lcs

# 示例
str1 = "ABABC"
str2 = "BABCA"
print("最长公共子串是:", longest_common_substring(str1, str2))

这段代码首先定义了一个二维数组counter来存储两个字符串的最长公共子串的长度信息。通过遍历两个字符串，当两个字符相等时，更新counter数组，并记录下最长公共子串的长度和结束位置。最后，根据记录的信息，从str1中截取最长公共子串并返回。

请注意，这个实现是针对两个字符串的最长公共子串问题。如果需要求解多个字符串的最长公共子串，算法会更加复杂，可能需要对每个字符串对都进行比较，然后找到所有字符串共有的最长子串。2 提到了求解多个字符串最长公共子串的问题，但具体的算法实现会有所不同。