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

Алгоритм Каркайнена-Сандерса (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].
   • Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит [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].

Заметим, что сортировка множества нечетных суффиксов [math] \{ S[i..n] | i \mod 2 == 1 \} [/math] аналогична сортировке множества пар [math] \{ (S[i], S[i+1..n]) | i \mod 2 == 1 \} [/math]. Однако [math] S[i+1..n] [/math] — четный суффикс, и его относительную позицию мы уже узнали на шаге 1, то есть свели задачу к сортировке [math] \{ (S[i], pos_e[i+1]) | i \mod 2 == 1 \} [/math], где [math] pos_e[i] [/math] — позиция суффикса [math] S[i..n] [/math] в [math]A_{S_e} [/math].

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив [math] A_{S_e} [/math]), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара [math] (S[n-1], n) [/math]. Псевдокод этого шага:

M = []
M.add(Pair(S[n-1], n))
for i = 0..n/2 - 1:
    if [math] A_{S_e}[i] [/math] == 0: //перед первым положительным суффиксом ничего не может стоять, поэтому пропускаем его
        continue 
    else:
        M.add(Pair(S[[math] A_{S_e}[i] [/math]-1], [math] A_{S_e}[i][/math]))

Заметим, что массив [math] M [/math] явно не отсортирован по вторым элементам, но главное — что он отсортирован по возрастанию соответствующих вторым элементам суффиксам. После устойчивой сортировки массива [math] M [/math] подсчетом по первому элементу легко восстановить массив [math] A_{S_o} [/math]:

[math] A_{S_o} [/math] = []
for i = 0..n/2 - 1:
   [math] A_{S_o} [/math].add(M[i].second - 1)

Получили, что весь второй шаг требует [math] O(n) [/math] времени.

Шаг 3

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

Пример

Покажем первые два шага агоритма для строки abaaab.

Во-первых, добавим защитный символ $, получив строку abaaab$. Во-вторых, дополним ее до четной длины, получив abaaab$$.

Шаг 1

1. В новом алфавите [math] \Sigma' [/math] будет три элемента — ab, aa, $$. Они получат номера 2, 1 и 0 соответственно.
2. Сжатой строкой [math] S' [/math] будет 2120.
3. После рекурсивного вызова получим, что [math] A_{S'} [/math] = [3, 1, 2, 0], и [math] A_{S_e} [/math] = [6, 2, 4, 0].

Шаг 2

1. Обойдя массив [math] A_{S_e} [/math], получим M = [(b, 6), (b, 2), (a, 4), ($, 8)].
2. После сортировки подсчетом по первому элементу, получим M = [($, 8), (a, 4), (b, 6), (b, 2)].
3. Восстановив массив [math] A_{S_o} [/math], получаем [7, 3, 5, 1], что действительно является суффиксным массивом для нечетных суффиксов.

Алгоритм 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: впилить описание сливания