1679
правок
Изменения
Нет описания правки
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
== Идея ==
Алгоритм базируется на алгоритме Фараха построения суффиксного дерева за линейное время:
# Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
# Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций.
# Сливаем суффиксные деревья за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
{{TODO| t = впилить описание первых двух шагов }}
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам.
В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным (почитать о том, как его делать, можно в статье D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays.).
== Алгоритм skew ==
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
# Построим суффиксный массив для суффиксов, соответствующих кратных трем позициям, используя результат первого шага за линейное время.
# Сливаем эти суффиксные массивы в один за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3n </tex>).
{{TODO| t = впилить описание сливания }}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
