1679
правок
Изменения
Нет описания правки
Алгоритм Каркайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
== Базовая идея ==
== Алгоритм «разделяй и властвуй» ==
{{Определение|definition='''Четным суффиксом''' назовем суффикс, начинающийся в четной позиции. <br>'''Нечетным суффиксом''' — суффикс, начинающийся в нечетной позиции.}} Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге сливания слияния мы сможем избавиться от него.
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов строки <tex> S </tex>.
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
# Построим суффиксный массив для суффиксов, соответствующих кратных кратным трем позициям, используя результат первого шага за линейное время.
# Сливаем эти суффиксные массивы в один за линейное время.
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \mod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S[i..i+2]; </tex> , где <tex> i \mod 3 \ne 0 </tex>, причем примем <tex> S[n-2..n] = S[n-2..n-1]\$ </tex>, а <tex> S[n-1..n+1] = S[n-1]\$\$ </tex>.
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S </tex> в строку <tex> S' </tex> длиной <tex> \frac23 n </tex> в алфавите <tex> \Sigma' </tex> следущим образом: <tex> S' = [ \Sigma'(s[i..i+2]) | i \mod 3 == 1 ] + [ \Sigma'(s[i..i+2]) | i \mod 3 == 2 ] </tex>. Суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \mod 3 == 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i \mod 3 == 2 </tex>, то строка <tex> S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] </tex>.
for i = 0..2n/3 - 1:
if <tex> A_{S_{12}}</tex>[i] % 3 == 1:
M.add(Pair(S[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i]))
stable_sort(M)
for i = 0..n/3 - 1:
Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 1 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Это аналогично сравнению пар <tex> (S[i], S[i+1..n-1]) </tex> и <tex> (S[j], S[j+1..n-1]) </tex>. Сравнить первые элементы пар мы можем за <tex> O(1) </tex>, а относительный порядок вторых элементов пар нам уже известен, так как они соотвествуют позициям, равным 2 и 1 по модулю 3 соответственно.
Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 2 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Тогда это аналогично сравнению троек <tex> (S[i], S[i+1], S[i+2..n-1]) </tex> и <tex> (S[j], S[j+1], S[j+2..n-1]) </tex>, что аналогично также можно делать за <tex> O(1) </tex>.
Псевдокод этой фазы:
<tex>A_{S}</tex> = []
// Вначале предподсчитаем за O(n) обратные перестановки для суффиксных массивов, то есть массивы Order order такие, что A[Orderorder[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
while i < 2 * n / 3 and j < n / 3:
pos12 = <tex> A_{S_{12}} </tex>[i]
pos0 = <tex> A_{0} </tex>[j]
if pos12 % 3 == 1:
if Pair(S[pos12], Order12order12[pos12 + 1]) < Pair(S[pos0], Order0order0[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
j++
else:
if Triple(S[pos12], S[pos12 + 1], Order12order12[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], Order0order0[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
i++
Таким образом, получили простой метод сливания слияния за <tex> O(n) </tex>.
== Ссылки ==
