Самая длинная повторная подстрока

Question

Обучение python, когда я иду на школьную работу. По сути, мне нужно найти самую длинную повторяющуюся подстроку в списке строк, как показано на рисунке here. Я читаю через this article и понимаю, что я должен делать.

до сих пор моя реализация выглядит следующим образом:

def long_rptr_subString(testList): 
    longSubstring = '' 

    if len(testList) > 1 and len(testList[0]) > 0: 
     for i in range(len(testList[0])): 
      for j in range(len(testList[0])-i+1): 
       if j > len(longSubstring) and all(testList[0][i:i+j] in x for x in testList): 
        longSubstring = testList[0][i:i+j] 
    return longSubstring 

теперь, когда я называю функцию с скажем ['slide', 'glidb', 'flidt', 'cridz', 'bidr'] я получить правильный результат 'id' как был мой самый длинный подстроки.

Однако, когда я передаю список ['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah'] Я не получаю никаких результатов. I должен вернуться 'blah' как моя самая длинная подстрока, но я не понял способ сделать это. Кажется, я могу только подбирать подстроки, когда они находятся во ВСЕХ элементах списка. Как я могу изменить свой код/​​логику, чтобы получить самую длинную подстроку, которая встречается более одного раза?

спасибо.

Answer 1

Вы можете соответствовать только подстрокам all элементов, потому что это именно то, что вы просите:

all(testList[0][i:i+j] in x for x in testList) 

Даже если вы меняете, что вы можете только найти самую длинную подстроку, которая находится в первой подстроки, потому что вы проверяете только testlist[0].

Вместо этого, попробовать что-то вроде:

def longest_substr(lst): 
    longest = None 
    for word in lst: 
     for i in range(len(word)): 
      for j in range(i+1, len(word)+1): 
       if ((longest is None or (j - i > len(longest))) and 
        sum(word[i:j] in w for w in lst) > 1): 
        longest = word[i:j] 
    return longest 

Это находит самую длинную подстроку, что это, по крайней мере, два (> 1) слов (или будет return None для пустого списка или списка пустых строк) и дает мне следующие результаты:

>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr']) 
'lid' 
>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']) 
'blah' 

Обратите внимание, что после того, как вы удалите требование о том, что подстрока должна быть во всех строках, самый длинный в первом списке слов, на самом деле 'lid'.

Answer 2

Если вы действительно хотите blah, вам необходимо удалить условие, что ваша самая длинная общая подпоследовательность должна быть во всех строках. Таким образом, вы можете это сделать (обратите внимание: вы получите lid для первого примера):

def allCommonSubstrings(s1, s2): 
    answer = set() 
    if len(s1) > len(s2): 
     s1, s2 = s2, s1 
    for i in range(len(s1)): 
     for j in range(i+1, len(s1)+1): 
      if s1[i:j] in s2: 
       answer.add(s1[i:j]) 
    return answer 

def longestCommonSubstring(strings): 
    common = set() 
    for s1,s2 in itertools.combinations(strings, 2): 
     common = common.union(allCommonSubstrings(s1, s2)) 
    return max(common, key=len) 

In [288]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']) 
Out[288]: 'blah' 

In [289]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr']) 
Out[289]: 'lid'