самая длинная общая подстрока python

Question

Учитывая список из k (k≤100) строк длиной не более 1000, найдите самую длинную общую подстроку из всех строк в данном списке.

Это основано на проблеме Розалинды.

---

Точное описание проблемы:

Общая подстрока набора строк - это подстрока каждого члена коллекция. Мы говорим, что общая подстрока является самой длинной общей подстрокой, если не существует более длинной общей подстроки. Например, «CG» является общей подстрокой «ACGTACGT» и «AACCGTATA», но это не настолько долго, насколько это возможно; в этом случае «CGTA» является самой длинной общей подстрокой «ACGTACGT» и «AACCGTATA».

Обратите внимание, что самая длинная общая подстрока не обязательно уникальна; для простого примера, «AA» и «CC» - это самые длинные общие подстроки «AA CC» и «CCAA».

Дано: набор из k (k≤100) строк ДНК длиной не более 1 кбит / с в формате FASTA.

Возврат: самая длинная общая подстрока в коллекции. (Если существует несколько решений, вы можете вернуть любое отдельное решение.) http://rosalind.info/problems/lcsm/

---

Я попытался написать прямую программу для этого. Я думал, что сделал это правильно, так как он работал на всех примерах, которые я бросил, но Розалинда говорит, что мой вывод неверен. Я думал об этом уже пару дней и думаю, что устал. Я был бы признателен за вторую пару глаз, чтобы помочь определить мою ошибку.

def get_lcs(string_list):
    string0 = string_list[0]
    n0 = len(string0)
    lcs = ''
    not_common_substrings = set()
    #pick a starting/ending index of the first string to
    #pick a potential common substring
    for i in range(n0):
        if len(lcs) > len(string0[i:]):
            break
        substring = ''
        substring_in = True
        for j in range(i, n0):
            if substring_in == False:
                break
            substring = string0[i:j+1]
            if substring in not_common_substrings:
                break

            #go through all the rest of the strings
            #in the list and see if our substring is a
            #common substring. If it is, and is longer than
            #the current longest common substring,
            #replace the current lcs with our substring
            if len(substring) < len(lcs):
                continue
            for string in string_list[1:]:
                if substring not in string:
 #optional          print(f'i={i}, j={j}, substring={substring} not in string={string}, lcs={lcs}\n')
                    not_common_substrings.add(substring)
                    substring_in = False
                    break
                else:
                    continue
            if substring_in == True:
                if len(substring) > len(lcs):
                    lcs = substring

    return lcs

Я включил комментарий, который раньше использовал, чтобы увидеть, нет ли подстроки в строке в списке, а затем распечатал, где подстрока есть и к какой строке он не принадлежит.

Я пробовал на различных примерах, вот список строк из rosalind: буфер обмена со списком строк

Моя программа вернул самую длинную общую подстроку 'A', но это неверно.

Когда я раскомментирую оператор печати в коде, я получаю

i=0, j=1, substring=AC not in string=TATCGGAAGTCGTAATGGTATAAGTTCGTTATCGAAGGCC, lcs=A

i=1, j=2, substring=CG not in string=GTTATGATGAACACATTTTATTAGCAGGTTGATCTGGTGG, lcs=A

i=2, j=3, substring=GC not in string=CTAATATCGGGAGATGTCATTTACAACTATATCTCACTGT, lcs=A

i=3, j=4, substring=CT not in string=TTGATCAAAGTATTTTCAAGAATGCGGCGGTTAAGTAGCGGGGGGTCCAACGGGTATTCG, lcs=A

i=4, j=5, substring=TC not in string=CTGGGGCGCACCCAGCTGAATTACTAAATAGATAATTACTACTTGGGGCCCGTTGTTACG, lcs=A

i=6, j=7, substring=TG not in string=GCAGATCCCGTCTAGGCGGGAAATCGGTAAGCCCTCCCTCTTTTCCAAACCCGAGGCATC, lcs=A

i=7, j=8, substring=GG not in string=TGAGCTGCCCTCAGAGAATCTGAAGTAGCGTGCTGAGTCTCGCACTGTGTAGCGAGTCAG, lcs=A

i=14, j=15, substring=GT not in string=CCTACTTCGAAGACCCTTCCCGACGCTGGCGGATAAATGCGACGGGGAGAACCTCTCTAT, lcs=A

i=15, j=16, substring=TA not in string=TGTCTGTCGCAGATTGCTTGGTGCCCTGGGCCGCAACATTCGACAGCGCGCATGAGGCAT, lcs=A

i=16, j=17, substring=AA not in string=GACCGTATATGCATTTAGACGATTCTTCGGAGACGGACTTATTAGACGACTTCCATTTTG, lcs=A

i=17, j=18, substring=AT not in string=AGCTCCCTCCTCGTCTTGTTTGAACGTAAGTCAGGTCGCAAAACCTTTAAAGGTCTCCAG, lcs=A

i=18, j=19, substring=TT not in string=TGAGCTGCCCTCAGAGAATCTGAAGTAGCGTGCTGAGTCTCGCACTGTGTAGCGAGTCAG, lcs=A

i=21, j=22, substring=AG not in string=TACTGAATATCGCTCGTCGGGCACGCTACCTATATGCTGTTATCACGTTGAACGAAATTT, lcs=A

i=24, j=25, substring=CA not in string=CCTACTTCGAAGACCCTTCCCGACGCTGGCGGATAAATGCGACGGGGAGAACCTCTCTAT, lcs=A

i=36, j=37, substring=GA not in string=TCAAACCATGTACTATCTCCTTAGCCTGTGCCAAAGTCCCCCTTAAGCCGCTCATGGTGG, lcs=A

i=40, j=41, substring=CC not in string=CTAATATCGGGAGATGTCATTTACAACTATATCTCACTGT, lcs=A

, что похоже на истину ...