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

Я знаком с алгоритмами LCS для 2 строк. Ищете предложения для поиска общих подстрок в строках 2..N. В каждой паре может быть несколько общих подстрок. В подмножествах строк могут быть разные общие подстроки.Алгоритм для поиска общей подстроки по 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)

источник

2010-03-10 Dwight Kelly

Это проблема конкуренции ACM, которая требует алгоритма с определенной производительностью? – Roman

Не будет ли подстрока «F» наиболее распространенной, поскольку она появляется в четырех строках? – interjay

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

Этот сор t делается все время в анализе последовательности ДНК. Вы можете найти для него множество алгоритмов. Имеется одна разумная коллекция here.

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

источник

2010-03-10 17:15:35

Пришел в значительной степени сказать, что это все время используется в вычислительной биологии. Однако определение «подстрока/подпоследовательность» часто неоднозначно (без преднамеренного для неалгоритмистов), и я думаю, что в этом случае его проблема требует, чтобы они были смежными. – Larry

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

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

источник

2010-03-10 17:31:48 luispedro

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

ответ

Смежные вопросы