Алгоритм поиска телескопизмов?

Question

[Radzhab]

Есть список слов

bulb
queen
dinosaur

Есть строка Bulbasaur. Как мы видим это составная часть двух слов выше - bulb и dinosaur.

lines = []
    fh = open('input.txt')
    for line in fh:
        lines.append(line.strip())
    fh.close()
    
    str = 'Bulbasaur'
    
    newlist = []
    
    for line in lines:
        if line in str.lower():
            newlist.append(line)
            str = str.replace(line,"")
    
    for line in lines:
        if str.lower() in line:
            newlist.append(line)
            str = str.replace(line,"")

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

Comments

[Dimonchik]

fh = open('input.txt')
    for line in fh:
        lines.append(line.strip())
    fh.close()

давно пора переучиться на with + readlines

остальные for - на list comprehentions

[Radzhab]

Проблема в том что я не знаю в каком порядке итоговый список выводить.

[sim3x]

Есть строка Bulbasaur. Как мы видим это составная часть двух слов выше - bulb и dinosaur.

bulb a saur
din o saur

Answer 1

[xmoonlight]

1. Представьте каждое слово, как граф (узел - буква).
2. Затем создайте общий граф, содержащий только уникальные части и связи между ними.
3. Ищите похожую структуру графа-слова внутри общего графа: непрерывные последовательности цепочек (узлов). Разрывы - сохраняете и продолжаете поиск с остановившегося узла.

На выходе - получите все возможные "склейки" последовательностей искомого слова.