1679
правок
Изменения
Нет описания правки
== Алгоритм ==
=== Шаг 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> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_e} </tex>. Очевидно, <tex> A_{S_e}[i] = 2 A_{S'}[i] </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.
=== Шаг 2 ===
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_o} </tex> для суффиксов строки, начинающихся в нечетных позициях, используя уже построенный <tex> A_{S_e} </tex>.
=== Шаг 3 ===
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам.
В случае суффиксного массива первый и второй шаги алгоритма делаются просто, а слияние становится очень сложным <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 ==
