Изменения

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

Рассматриваемый алгоритм состоит из примерно <tex>\lceil\log n\rceil + 1</tex> фазитераций. На <tex>k</tex>-той фазе итерации (<tex>k=0..\lceil\log n\rceil </tex>) сортируются циклические подстроки длины <tex>2^k</tex>. На последней, <tex>\lceil\log n\rceil</tex>-ой фазеитерации, будут сортироваться подстроки длины <tex>2^{\lceil\log n\rceil} \ge n</tex>, что эквивалентно сортировке циклических сдвигов.

На каждой фазе итерации алгоритм помимо перестановки <tex>p[0..n-1]</tex> индексов циклических подстрок будет поддерживать для каждой циклической подстроки длиной <tex>2^k</tex>, начинающейся в позиции <tex>i</tex>, номер класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности <tex>c[i]</tex> будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.

На нулевой фазе итерации мы должны отсортировать циклические подстроки длины <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>.

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

\multicolumn{3}{|l|}{0 stepiteration} & \multicolumn{4}{l|}{1 stepiteration} & \multicolumn{4}{l|}{2 stepiteration} & \multicolumn{4}{l|}{3 stepiteration} \\ \hline