Помощь - Поиск - Пользователи - Календарь
Полная версия: Максимальное совпадение двух строк
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
Unconnected
Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду.
Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек..
TarasBer
http://e-maxx.ru/algo/suffix_automata#27
Анон
Цитата(Unconnected @ 8.10.2012 3:22) *

Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду.
Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек..



А что это за алгоритм такой? На 100 строках сработает?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.