Изменения
Нет описания правки
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
{{Определение
|definition=
'''Четным суффиксом''' назовем суффикс, начинающийся в четной позиции. <br>
'''Нечетным суффиксом''' — суффикс, начинающийся в нечетной позиции.
}}
== Базовая идея ==
Алгоритм базируется на алгоритме Фараха<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> построения суффиксного дерева за линейное время:
# Строим суффиксное дерево для четных суффиксов, начинающихся в четных позициях, рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.# Строим суффиксное дерево для нечетных суффиксов, начинающихся в нечетных позициях за линейное время, используя результат для четных позиций.
# Сливаем суффиксные деревья за линейное время.
== Алгоритм ==
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец).
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_e} </tex> для суффиксов строки <tex> S </tex>, начинающихся в четных позициях.
# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \frac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[2i]S[2i + 1] </tex>, где <tex> i \in [0; n / 2) </tex>. {{TODO| t=что делать с четностью?}}
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
=== Шаг 2 ===
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_o} </tex> для суффиксов строки, начинающихся в нечетных позициях, используя уже построенный <tex> A_{S_e} </tex>. Заметим, что сортировка множества нечетных суффиксов <tex> \{ S[i..n] | i \mod 2 == 1 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \mod 2 == 1 \} </tex>. Однако <tex> S[i+1..n] </tex> — четный суффикс, и его относительную позицию мы уже узнали на шаге 1, то есть свели задачу к сортировке <tex> \{ (S[i], pos_e[i+1]) | i \mod 2 == 1 \} </tex>, где <tex> pos_e[i] </tex> — позиция суффикса <tex> S[i..n] </tex> в <tex>A_{S_e} </tex>. Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_e} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара <tex> (S[n-1], n) </tex>. Псевдокод этого шага: M = [] M.add(Pair(S[n-1], n)) for i = 0..n/2 - 1: if <tex> A_{S_e}[i] </tex> == 0: //перед первым положительным суффиксом ничего не может стоять, поэтому пропускаем его continue else: M.add(Pair(S[<tex> A_{S_e}[i] </tex>-1], <tex> A_{S_e}[i]</tex>)) Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементам, но главное — что он отсортирован по возрастанию соответствующих вторым элементам суффиксам. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_o} </tex>: <tex> A_{S_o} </tex> = [] for i = 0..n/2 - 1: <tex> A_{S_o} </tex>.add(M[i].second - 1) Получили, что весь второй шаг требует <tex> O(n) </tex> времени.
=== Шаг 3 ===
