Изменения
→Описание алгоритма
На нулевой фазе мы должны отсортировать циклические подстроки длины <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)</tex> выполнять следующую, <tex>k-</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>(c[i], c[i + 2^{k-1}])</tex>.
