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