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

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

Идея

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

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

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

TODO: впилить описание первых двух шагов

Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным (почитать о том, как его делать, можно в статье D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays.).

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