1679
правок
Изменения
→Алгоритм
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
== Алгоритм «разделяй и властвуй» ==
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге сливания мы сможем избавиться от него.
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_eS_o} </tex> для нечетных суффиксов строки <tex> S </tex>, начинающихся в четных позициях.
# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \frac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[2i]S[2i i..i + 1] </tex>, где <tex> i \in mod 2 == 1 </tex>, причем обозначим <tex> S[0; n -1..n] </ 2) tex> как <tex> S[n-1]\$</tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_eS_o} </tex>. Очевидно, <tex> A_{S_eS_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.
=== Шаг 2 ===
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_oS_e} </tex> для нечетных четных суффиксов, используя уже построенный <tex> A_{S_eS_o} </tex>.
Заметим, что сортировка множества нечетных четных суффиксов <tex> \{ S[i..n] | i \mod 2 == 1 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \mod 2 == 1 0 \} </tex>. Однако <tex> S[i+1..n] </tex> — четный нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_eS_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара <tex> (S[n-1], n) </tex>. Псевдокод этого шага:
M = []
for i = 0..n/2 - 1:
Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементам и хранит не суффиксы, а их позиции в строке <tex> S </tex>, но главное — что он отсортирован по возрастанию соответствующих этим позициям четным нечетным суффиксам. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_oS_e} </tex>: stable_sort(M) <tex> A_{S_oS_e} </tex> = []
for i = 0..n/2 - 1:
<tex> A_{S_oS_e} </tex>.add(M[i].second - 1)
=== Пример ===
Покажем первые два шага агоритма для строки '''abaaabbbaaabab'''.
Во-первых, добавим защитный символ $, получив строку '''abaaabbbaaabab$'''. Во-вторых, дополним ее до четной длины, получив '''abaaabbbaaabab$$'''.
==== Шаг 1 ====
# В новом алфавите <tex> \Sigma' </tex> будет три четыре элемента — '''abba''', '''aa''', '''b$''', '''$$'''. Они После сортировки они получат номера 23, 1 , 2 и 0 соответственно.# Сжатой строкой <tex> S' </tex> будет '''212031320'''.# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [34, 1, 23, 0, 2], и <tex> A_{S_e} </tex> = [69, 3, 27, 41, 05].
==== Шаг 2 ====
# Обойдя массив <tex> A_{S_eS_o} </tex>, получим M = [('''b$''', 69), ('''ba''', 23), ('''a''', 47), ('''b''', 1), ('''$a''', 85)].# После сортировки подсчетом по первому элементу, получим M = [('''$''', 89), ('''a''', 3), ('''a''', 47), ('''ba''', 65), ('''b''', 21)].# Восстановив массив <tex> A_{S_oS_e} </tex>, получаем [78, 2, 36, 54, 10], что действительно является суффиксным массивом для нечетных четных суффиксов.
== Алгоритм Каркайнена-Сандерса ==
