Python中字符串的最大公约数

Question

我想要一个Python函数，给定一个列表

mystrings = ['abcde', 'abcdf', 'abcef', 'abcnn']

能够返回字符串'abc'，也就是说，返回这个列表中所有元素都包含的最长的字符串。我有一个解决方案，就是通过循环检查mystring[0]的所有子串，然后和其他元素进行比较，一旦找到第一个不匹配的子串就退出循环。不过，我觉得应该有更高效、更优雅、更符合Python风格的方法来实现这个功能。

有人能告诉我怎么正确地做到这一点吗？

Answer 1

一旦你明白“最长公共子串”就是你所描述的问题，那就很容易找到你想要的东西了：

例如，来自维基教科书：

def LongestCommonSubstring(S1, S2):
    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
    longest, x_longest = 0, 0
    for x in xrange(1,1+len(S1)):
        for y in xrange(1,1+len(S2)):
            if S1[x-1] == S2[y-1]:
                M[x][y] = M[x-1][y-1] + 1
                if M[x][y]>longest:
                    longest = M[x][y]
                    x_longest  = x
            else:
                M[x][y] = 0
    return S1[x_longest-longest: x_longest]

Answer 2

你描述的方式是，你想要从开始的位置找到最长的子字符串：

>>> os.path.commonprefix(['abcde', 'abcdf', 'abcef', 'abcnn'])
'abc'