1679
правок
Изменения
→Алгоритм
== Алгоритм ==
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге сливания мы сможем избавиться от него.
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_e} </tex> для суффиксов строки <tex> S </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>. Однако простой модификацией алгоритма можно значительно упростить его.
=== Пример ===
Покажем первые два шага агоритма для строки '''abaaab'''.
Во-первых, добавим защитный символ $, получив строку '''abaaab$'''. Во-вторых, дополним ее до четной длины, получив '''abaaab$$'''.
==== Шаг 1 ====
# В новом алфавите <tex> \Sigma' </tex> будет три элемента — '''ab''', '''aa''', '''$$'''. Они получат номера 2, 1 и 0 соответственно.
# Сжатой строкой <tex> S' </tex> будет '''2120'''.
# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [3, 1, 2, 0], и <tex> A_{S_e} </tex> = [6, 2, 4, 0].
==== Шаг 2 ====
# Обойдя массив <tex> A_{S_e} </tex>, получим M = [('''b''', 6), ('''b''', 2), ('''a''', 4), ('''$''', 8)].
# После сортировки подсчетом по первому элементу, получим M = [('''$''', 8), ('''a''', 4), ('''b''', 6), ('''b''', 2)].
# Восстановив массив <tex> A_{S_o} </tex>, получаем [7, 3, 5, 1], что действительно является суффиксным массивом для нечетных суффиксов.
== Алгоритм skew ==
