Изменения
→Алгоритм, использующий хеши
Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{---}} сократить оценку времени сравнения двух циклических сдвигов до <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>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов. Зная посчитанные хеши префиксов исходной строки, легко найти хеш префикса циклического сдвига, так как он является конкатенацией двух префиксов исходной строки.
Если оказалось, что <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>.
