Изменения
→Алгоритм за O(N^2 log(N)) (наивно)
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex> воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда время на сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритмы составит <tex>O(N^2\log(N))</tex>.
=== Псевдокод ===
suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
'''sort''' (suf, compare)
'''compare''' (<tex>j_1</tex>, <tex>j_2</tex>)
'''for''' <tex>i</tex> = 0 '''to''' <tex>|s|</tex> '''do'''
'''if''' (s[(<tex>j_1+i</tex>) '''mod''' <tex>|s|</tex>] > s[(<tex>j_2+i</tex>) '''mod''' <tex>|s|</tex>])
'''ret''' 1
'''if''' (s[(<tex>j_1+i</tex>) '''mod''' <tex>|s|</tex>] < s[(<tex>j_2+i</tex>) '''mod''' <tex>|s|</tex>])
'''ret''' -1
'''ret''' 0
== Алгоритм за O(N log^2(N)) (хэши) ==
