74
правки
Изменения
м
→Алгоритм «разделяй и властвуй»
# Сливаем суффиксные массивы за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T\left(\fracdfrac{n}{2}\right) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге слияния мы сможем избавиться от него.
На первом шаге мы строим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов строки <tex> S </tex>.
# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \fracdfrac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[i..i + 1] </tex>, где <tex> i \bmod 2 = 1 </tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
