Алгоритм Карккайнена-Сандерса

Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения суффиксного массива за линейное время.

Базовая идея

Алгоритм базируется на алгоритме Фараха построения суффиксного дерева за линейное время:

1. Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
2. Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций.
3. Сливаем суффиксные деревья за линейное время.

Получили асимптотическое уравнение [math] T(n) = T(\frac{n}{2}) + O(n) [/math], решением которого является [math] T(n) = O(n) [/math].

Алгоритм

Шаг 1

На первом шаге мы строим суффиксный массив [math] A_{S_e} [/math] для суффиксов строки [math] S [/math], начинающихся в четных позициях.

1. Отобразим исходную строку [math] S [/math] длины [math] n [/math] в строку [math] S' [/math] длины [math] \frac{n}{2} [/math] следующим образом:
   • Сделаем список, состоящий из пар символов вида [math] S[2i]S[2i + 1] [/math], где [math] i \in [0; n / 2) [/math].

TODO: что делать с четностью?

1. • Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит [math] \Sigma' [/math].
   • Перекодируем строку [math] S [/math] в алфавит [math] \Sigma' [/math], получив строку [math] S' [/math] половинной длины.
2. Рекурсивно построим суффиксный массив [math] A_{S'} [/math].
3. Построим суффиксный массив [math] A_{S_e} [/math]. Очевидно, [math] A_{S_e}[i] = 2 A_{S'}[i] [/math], так отношение упорядоченности любых двух строк в старом алфавите [math] \Sigma [/math] эквивалентно отношению упорядоченности в новом алфавите [math] \Sigma' [/math] по его построению.

Шаг 2

На этом шаге мы за линейное время получим суффиксный массив [math] A_{S_o} [/math] для суффиксов строки, начинающихся в нечетных позициях, используя уже построенный [math] A_{S_e} [/math].

Шаг 3

Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. В случае суффиксного массива слияние становится очень сложным . Однако простой модификацией алгоритма можно значительно упростить его.

Алгоритм skew

Изменим изначальный алгоритм следующим образом:

1. Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
2. Построим суффиксный массив для суффиксов, соответствующих кратных трем позициям, используя результат первого шага за линейное время.
3. Сливаем эти суффиксные массивы в один за линейное время.

Получили асимптотическое уравнение [math] T(n) = T(\frac23 n) + O(n) [/math], решением которого также является [math] T(n) = O(n) [/math] (это видно из того, что сумма геометрической прогрессии с основанием [math] \frac23 [/math] равна [math] 3n [/math]).

TODO: впилить описание сливания