如何在Python中从两个以上的字符串中找出最长的公共子字符串？

在Python中，经常需要在多个字符串中找出它们之间最长的公共子字符串。这种操作在字符串处理，文本相似度匹配，数据挖掘等领域都有广泛的应用。

暴力破解法

最简单直接的方法是暴力枚举法，即枚举所有的子串，判断其是否为所有字符串的公共子串，并记录最长的那一个。具体步骤如下：

枚举所有字符串的子串
判断该子串是否为所有字符串的公共子串
如果是，判断是否比当前最长的公共子串更长，如果更长则更新
得到最长的公共子串

下面是Python实现：

def longest_common_substring(strs):
    """
    找出多个字符串中的最长公共子字符串
    """
    def is_common(prefix):
        """
        判断prefix是否为所有字符串的公共前缀
        """
        return all(s.startswith(prefix) for s in strs)

    n, m = len(strs), len(min(strs, key=len))
    ans = ""
    for i in range(m):
        for j in range(i+1, m+1):
            prefix = strs[0][i:j]
            if is_common(prefix):
                if len(prefix) > len(ans):
                    ans = prefix
    return ans

该算法的时间复杂度为 $O(n^3m^2)$ ，其中 $n$ 为字符串个数， $m$ 为字符串中最短的长度。

动态规划法

暴力破解法的时间复杂度较高，不能处理较长的字符串。下面介绍一种时间复杂度较低的动态规划方法。

令 $f[i][j]$ 表示以第一个字符串的第 $i$ 个字符结尾，以第二个字符串的第 $j$ 个字符结尾的最长公共子字符串的长度。

则有如下转移方程：

$f[i][j] = \begin{cases} 0&i=0\mbox{或}j=0\ f[i-1][j-1]+1&s1[i-1]=s2[j-1]\ 0&\mbox{otherwise} \end{cases}$

其中 $s1$ 和 $s2$ 分别表示要比较的两个字符串。找到最长公共子字符串的长度后，可以根据该长度返回相应的子串。

下面是Python实现：

def longest_common_substring(strs):
    """
    找出多个字符串中的最长公共子字符串
    """
    def lcs(s1, s2):
        """
        求两个字符串的最长公共子字符串
        """
        m, n = len(s1), len(s2)
        f = [[0] * (n+1) for _ in range(m+1)]
        ans = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s1[i-1] == s2[j-1]:
                    f[i][j] = f[i-1][j-1] + 1
                    ans = max(ans, f[i][j])
        return ans

    n = len(strs)
    if n == 0: return ""
    if n == 1: return strs[0]
    ans = lcs(strs[0], strs[1])
    for i in range(2, n):
        ans = lcs(ans, strs[i])
    return ans

该算法的时间复杂度为 $O(nm^2)$ ，其中 $n$ 为字符串个数， $m$ 为字符串的长度。

示例

下面是一些测试用例：

assert longest_common_substring(["flower","flow","flight"]) == "fl"
assert longest_common_substring(["dog","racecar","car"]) == ""
assert longest_common_substring(["a","a","b"]) == "a"
assert longest_common_substring([]) == ""
assert longest_common_substring(["apple","banana"]) == ""