Алгоритм цифровой сортировки суффиксов циклической строки

Эта статья находится в разработке!

Дана строка [math]s[/math]. Требуется отсортировать все её суффиксы. Поскольку мы сортируем циклические сдвиги, то и подстроки мы будем рассматривать циклические: под подстрокой [math]s[i..j][/math], когда [math]i \gt j[/math], понимается подстрока [math]s[i..n-1] + s[0..j][/math]. Кроме того, предварительно все индексы берутся по модулю длины строки.

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

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

Перейдём теперь к более подробному описанию алгоритма

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

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

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