1679
правок
Изменения
→Алгоритм skew
# Восстановив массив <tex> A_{S_o} </tex>, получаем [7, 3, 5, 1], что действительно является суффиксным массивом для нечетных суффиксов.
== Алгоритм skew Каркайнена-Сандерса ==
Изменим изначальный алгоритм следующим образом:
# Построим суффиксный массив для суффиксов, соответствующих не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.
<tex>A_{S_0}</tex> = []
M = []
for i = 0..2n/3- 1:
if <tex> A_{S_{12}}</tex>[i] % 3 == 1:
M.add(Pair(S[A_{S_{12}}</tex>[i] - 1], A_{S_{12}}</tex>[i]))
stable_sort(M)
for i = 0..n/3- 1:
<tex>A_{S_0}</tex>.add(M[i].second - 1)
Аналогично, второй шаг требует <tex> O(n) </tex> времени.
=== Шаг 3 ===
На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>.
Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но сотвествующие элементам массива суффиксы — отсортированы.
Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <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 такие, что A[Order[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
Order12 = inverse(<tex>A_{S_{12}}</tex>)
Order0 = inverse(<tex>A_{S_0}</tex>)
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], Order12[pos12 + 1]) < Pair(S[pos0], Order0[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
else:
<tex>A_{S}</tex>.add(pos0)
j++
else:
if Triple(S[pos12], S[pos12 + 1], Order12[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], Order0[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
else:
<tex>A_{S}</tex>.add(pos0)
j++
while i < 2 * n / 3:
<tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])
i++
while j < n / 3:
<tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j])
i++
Таким образом, получили простой метод сливания за <tex> O(n) </tex>.
== Ссылки ==
