Алгоритм поиска одинаковых участков в N строках?

Question

[Anastasiya Sila]

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

Допустим есть несколько строк (5, 10, 15..) абсолютно произвольного вида и произвольной длины, для простоты возьмем так:
ABCBDCEACA,
BCDСEAEDAD,
CAEDСECDAE ... и т.д.

Каким образом можно найти последовательность символов(максимально длинную, конечно), которая есть во всех строках, если она заранее неизвестна?
Подстрока в примере получается DCE, но как это определить с помощью программы, никакого подобного алгоритмы я пока не нашла...или плохо искала?

Answer 1

[⚡ Kotobotov ⚡]

хехех, незнаю почему не любят использовать алгоритм Ахо-Карасик, по-моему наиболее удобный для таких целей
очень легко будет найти самую длинную ветку в дереве.

Answer 2

[gleb_kudr]

Подобные алгоритмы чрезвычайно широко используются в биоинформатике. Вот направление для начала поисков en.wikipedia.org/wiki/BLAST

Comments

[Anastasiya Sila]

о, спасибо, посмотрим)

Answer 3

[DnAp]

Посмотрите в этой статье на раздел "Как это работает".
Там описано направление в котором я бы двигался для написания такого алгоритма

Answer 4

[GavriKos]

Вам нужен какой то оптимальный алгоритм? Неоптимально решается путем перебора всех подстрок из первой строки и поиском их в остальных.

Comments

[Anastasiya Sila]

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

[GavriKos]

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