Изменения

Дана циклическая строка <tex>s[0 .. n - 1]</tex>. Суффиксом циклической строки <tex>s</tex> называется строка <tex>s[i .. n - 1] + s[0 .. i - 1], i < n </tex>(будем называть такую строкую суффиксом под номером i). Требуется отсортировать все её суффиксы в порядке лексикографической сортировки.

На нулевой итерации мы должны отсортировать отсортируем циклические подстроки длины <tex>1</tex>, т.е. первые символы строк, и разделить разделим их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой При помощи [[Сортировка подсчетом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим |сортировки подсчетом]] построим массив <tex>p</tex>, содержащий номера суффиксов, отсортированных в лексикографическом порядке. После этого проходом по По этому массиву <tex>p</tex> и сравнением символов строится построим массив классов эквивалентности <tex>c</tex>.

Пусть мы выполнили На <tex>k-1</tex>-ю итерацию (т.е. вычислили значения массивов ой итерации имеем массивы <tex>p</tex> и <tex>c</tex> для неё), вычисленные на предыдущей итерации. Научимся за Приведем алгоритм, выполняющий <tex>O(n)k</tex> выполнять -ую итерацию за <tex>kO(n)</tex>-ю итерацию. Поскольку итераций всего <tex>O(\log n)</tex>, это даст нам требуемый такой алгоритм с временем имеет асимптотику <tex>O(n \log n)</tex>.

Заметим, что циклическая подстрока длины <tex>2^k</tex> состоит из двух подстрок длины <tex>2^{k-1}</tex>, которые мы можем сравнивать между собой за <tex>O(1)</tex>, используя информацию с предыдущей итерации — номера классов эквивалентности <tex>c</tex>. Таким образом, для подстроки длины <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, вся необходимая информация содержится в паре чисел <tex>(\textless c[i], c[i + 2^{k-1}])\textgreater </tex>.

Это даёт нам весьма простое решение: отсортировать Отсортируем подстроки длины <tex>2^k</tex> просто по этим данным парам чисел, это и даст нам требуемый запишем порядок, т.е. в массив <tex>p</tex>. Воспользуемся здесь приёмом, на котором основана [[Цифровая сортировка| цифровая сортировка]]: чтобы отсортировать отсортируем пары, отсортируем их сначала по вторым элементам, а затем — по первым элементам (обязательно устойчивой сортировкой). Однако отдельно вторые элементы уже упорядочены — этот порядок задан в массиве от предыдущей итерации. Тогда, чтобы упорядочить пары получить порядок пар по вторым элементам, надо просто от каждого элемента массива <tex>p</tex> отнять <tex>2^{k-1}</tex> — это даст нам порядок сортировки пар по вторым элементам (<tex>p</tex> даёт упорядочение подстрок длины <tex>2^{k-1}</tex>, и при переходе к строке вдвое большей длины эти подстроки становятся их вторыми половинками, поэтому от позиции второй половинки отнимается длина первой половинки).

Таким образом, мы производим сортировку по вторым элементам пар. Теперь надо Чтобы произвести устойчивую сортировку по первым элементам пар, её уже можно выполнить за воспользуемся сортировкой подсчетом, имеющую асимптотику <tex>O(n)</tex> с помощью сортировки подсчётом.

Осталось только пересчитать номера классов эквивалентности <tex>c</tex>, просто пройдя по полученной новой перестановке <tex>p</tex> и сравнивая соседние элементы (опять же, сравнивая как пары двух чисел).

'''if''' suffs[i] < cur_len sorted_by2[i] = (suffs[i] + str.length() - cur_len '''else''' sorted_by2[i] = suffs[i] - cur_len) % str.length