Алгоритм для нахождения общей подстроки через строки N
Я знаком с алгоритмами 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 ответа
Подобные вещи постоянно выполняются в анализе последовательности ДНК. Вы можете найти для этого множество алгоритмов. Один разумный набор перечислен здесь .
Есть также грубый- силовой подход создания таблиц из каждой подстроки (если вас интересуют только короткие): сформировать N-арное дерево (N = 26 для букв, 256 для ASCII) на каждом уровне и сохранить гистограммы от счетчика на каждом узле. Если вы отсечете мало используемые узлы (чтобы сохранить разумные требования к памяти), вы получите алгоритм, который находит все подпоследовательности длиной до M в чем-то вроде N * M ^ 2 * log ( M) время для ввода длины N. Если вместо этого вы разделите его на K sepa оценивая строки, вы можете построить древовидную структуру и просто прочитать ответ (ы) за один проход по дереву.
Суффикс-деревья - это ответ, если у вас нет действительно больших строк, где память становится проблемой. Ожидайте использования памяти 10 ~ 30 байтов на символ в строке для хорошей реализации. Также есть несколько реализаций с открытым исходным кодом, которые облегчают вашу работу.
Есть и другие, более лаконичные алгоритмы, но их труднее реализовать (ищите «сжатые суффиксные деревья»).