1679
правок
Изменения
Нет описания правки
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
== Идея Базовая идея ==Алгоритм базируется на алгоритме Фараха <ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> построения суффиксного дерева за линейное время:
# Строим суффиксное дерево для суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
# Строим суффиксное дерево для суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций.
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам.
В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным (почитать о том, как его делать, можно в статье <ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays.)http://www.springerlink.com/content/568156021q45r320/</ref>.
== Алгоритм skew ==
{{TODO| t = впилить описание сливания }}
== Ссылки ==
<references />
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]
