Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду.
Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек..
Полная версия: Максимальное совпадение двух строк
Цитата(Unconnected @ 8.10.2012 3:22) 
Дано 10 строк из латинских lowcase символов, каждая строка до 10 000 символов. Нужно найти максимальную общую подстроку, за секунду.
Есть алгоритм, работающий для двух строк за O(mn). Думал найти все общие подстроки для двух строк, а потом искать (за O(n)) каждую подстроку в других строках, дактилоскопическим методом, или КМП.. но это всё равно как-то долго. Потом нашел в сети алгоритм, работающий за m*n*log(m) (m длины, n кол-во строк), и он на 10 строках по 10к символов работает 5 сек..
А что это за алгоритм такой? На 100 строках сработает?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.