Алгоритм поиска общей подстроки в N строках - PullRequest
Новая
       16

Алгоритм поиска общей подстроки в N строках

8 голосов
/ 10 марта 2010

Я знаком с алгоритмами LCS для 2 строк. Поиск предложений по поиску общих подстрок в строках 2..N. В каждой паре может быть несколько общих подстрок. В подмножествах строк могут быть разные общие подстроки.

строки: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

общие строки: 

1/2 (DEF)
1/3 (ABCDEF)
1/4 (IJKL)
1/5 (FGH)
2/3 (DEF)

самые длинные общие строки: 

1/3 (ABCDEF)

Наиболее распространенные строки: 

1/2/3 (DEF)

Ответы [ 2 ]

6 голосов
/ 10 марта 2010

Такого рода вещи делаются постоянно при анализе последовательности ДНК. Вы можете найти множество алгоритмов для этого. Одна разумная коллекция перечислена здесь .

Существует также грубый метод создания таблиц из каждой подстроки (если вас интересуют только короткие): сформируйте N-арное дерево (N = 26 для букв, 256 для ASCII ) на каждом уровне и хранить гистограммы счета на каждом узле. Если вы удалите малоиспользуемые узлы (чтобы сохранить разумные требования к памяти), вы получите алгоритм, который находит все подпоследовательности длины до M за время N * M ^ 2 * log (M) для ввода длины N. Если вместо этого вы разбиваете это на K отдельных строк, вы можете построить древовидную структуру и просто прочитать ответ (ы) за один проход по дереву.

1 голос
/ 10 марта 2010

Деревья суффиксов являются ответом, если у вас нет действительно больших строк, где память становится проблемой. Ожидайте 10 ~ 30 байт использования памяти на символ в строке для хорошей реализации. Также есть пара реализаций с открытым исходным кодом, которые облегчают вашу работу.

Существуют и другие, более короткие алгоритмы, но их сложнее реализовать (ищите «сжатые суффиксные деревья»).

...