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

Материал из Викиконспекты
Перейти к: навигация, поиск

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