Изменения
→Алгоритм за O(N log^2(N)) (хэши)
== Алгоритм за O(N log^2(N)) (хэши) ==
Данный алгоритм является некоторым улучшением предыдущего. Основная цель - сократить оценку времени сравнения двух циклических сдвигов до <tex>O(log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N log^2(N))</tex>. Для этого вычислим хэши всех префиксов строки <tex>\alpha\$</tex> за <tex>O(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>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хэшей префиксов.
Если оказалось, что <tex>lcp(i_1,i_2) = N</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < N</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. И так двоичный поиск работает за <tex>O(log(N))</tex> остальные операции требуют константного времени, получаем оценку времени, необходимого на сравнение двух циклических сдвигов <tex>O(log(N))</tex>.
=== Псевдокод ===
suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
'''sort''' (suf, compare)
'''compare''' (<tex>j_1</tex>, <tex>j_2</tex>)
same <tex>\leftarrow</tex> '''lcp'''(<tex>j_1</tex>, <tex>j_2</tex>)
'''ret''' s[<tex>j_1</tex> + same] - s[<tex>j_2</tex> + same]
'''lcp''' (<tex>j_1</tex>, <tex>j_2</tex>)
<tex>l</tex> <tex>\leftarrow</tex> <tex>-1</tex>
<tex>r</tex> <tex>\leftarrow</tex> <tex>|S|+1</tex>
'''while''' (<tex>r - l > 1</tex>)
<tex>m</tex> <tex>\leftarrow</tex> <tex>(r + l) / 2</tex>
'''if''' (hash[<tex>j_1\dots j_1 +m</tex>] = hash[<tex>j+2\dots j_2 + m</tex>])
<tex>l \leftarrow m </tex>
'''else'''
<tex> r \leftarrow m </tex>
'''ret''' <tex>l</tex>
== Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов) ==
