Python中字符串的最大公约数

Question

我希望有一个Python函数，它可以接受列表作为参数。

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

返回字符串“abc”，即列表中所有元素都包含的最长片段。我有一个解决方案，它只是循环遍历mystring [0]的切片，并将其与其余部分进行比较，并在找到第一个不匹配的子字符串时退出循环。然而，我怀疑一定有更高效、更优雅和更pythonic的方法来做到这一点。

有人能指出如何正确地做到这一点吗？

- v923z

---

请查看http://en.wikipedia.org/wiki/Longest_common_substring_problem。 - NPE

Answer 1

根据您的描述，您想要从起始点开始的最大子字符串：

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

- JBernardo

---

不，他搜索的是公共子串，而不是公共前缀。 - Martin Thurau

抱歉，如果我在原始帖子中表达不清：我想找到最长的公共前缀，所以Bernardo的解决方案正是我要找的。非常感谢！ - v923z

Answer 2

一旦你意识到所描述的问题是“最长公共子串”，就很容易找到你想要的：

例如，从Wikibooks中可以得到如下信息：

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]

- jwd

---

这是一种朴素的方法。此外，它仅适用于两个字符串。 - Sven Marnach

谢谢，但这个解决方案和我的原始解决方案一样复杂 :( - v923z