Наибольший общий делитель для строк в Python

Question

Я хотел бы иметь функцию Python, которая дает список

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

возвращает строку 'abc', т. Е. Самый длинный фрагмент, содержащийся из всех элементов в списке.У меня есть решение, которое просто перебирает кусочки mystring[0], сравнивает его с остальными и прерывает цикл всякий раз, когда обнаруживается первая несоответствующая подстрока.Тем не менее, я подозреваю, что должен быть более эффективный, элегантный и питонный способ сделать это.

Может кто-нибудь указать, как это сделать правильно?

Answer 1

Как вы описали, вам нужна самая большая подстрока в начальной точке:

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

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]