Бюрократы, editor, Администраторы
422
правки
Изменения
м
Нет описания правки
== Алгоритм за O(N log^2(N)) (хеши) ==
Данный алгоритм является некоторым улучшением предыдущего. Основная цель - сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N \log^2(N))</tex>. У нас есть возможность быстро сравнивать на равенство подстроки используя метод, описанный в [[Поиск_подстроки_в_строке_с_использованием_хеширования._Алгоритм_Рабина-Карпа | здесь]].
Далее пусть нам необходимо сравнить два циклических сдвига <tex>s[i_1..i_1-1]</tex> и <tex>s[i_2..i_2-1]</tex>. Найдем сначала их наибольший общий префикс (<tex>lcp(i_1,i_2)</tex>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов.
