Изменения
→Алгоритм за O(N \log^2(N)) (префиксы циклических сдвигов)
'''ret''' <tex>l</tex>
== Алгоритм за <tex>'''O(N \log^2(N))'''</tex> (префиксы циклических сдвигов) ==
Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за <tex>O(N \log(N))</tex>. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины <tex>1,2,4,..., 2^{\lceil \log_2(n)\rceil}</tex>. Еще одно важное дополнение: после каждой фазы каждому префиксу циклического сдвига <tex>s[i..i-1]</tex> будет присваиваться номер класса эквивалентности <tex>c[i]</tex> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.
