IPB
ЛогинПароль:

> Максимальное совпадение двух строк
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 19:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name