Изменения
Нет описания правки
{{В разработке}}
== Постановка задачи ==
Дана строка <tex>s</tex>. Требуется отсортировать все её суффиксы. Поскольку мы сортируем циклические сдвиги, то и подстроки мы будем рассматривать циклические: под подстрокой <tex>s[i..j]</tex>, когда <tex>i > j</tex>, понимается подстрока <tex>s[i..n-1] + s[0..j]</tex>. Кроме того, предварительно все индексы берутся по модулю длины строки.
== Решение ==
Рассматриваемый алгоритм состоит из примерно <tex>\log n</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>i</tex> с длиной <tex>2^k</tex>, номер класса эквивалентности <tex>c[i]</tex>, которому эта подстрока принадлежит. В самом деле, среди подстрок могут быть одинаковые, и алгоритму понадобится информация об этом. Кроме того, номера классов эквивалентности <tex>c[i]</tex>, будем давать таким образом, чтобы они сохраняли и информацию о порядке: если один суффикс меньше другого, то и номер класса он должен получить меньший.
На нулевой фазе мы должны отсортировать циклические подстроки длины <tex>1</tex>, т.е. отдельные символы строки, и разделить их на классы эквивалентности (одинаковые символы должны быть отнесены к одному классу эквивалентности). Это можно сделать сортировкой подсчётом. Для каждого символа посчитаем, сколько раз он встретился. Потом по этой информации восстановим массив <tex>p</tex>. После этого, проходом по массиву <tex>p</tex> и сравнением символов, строится массив <tex>c</tex>.
