74
правки
Изменения
м
→Шаг 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>.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
rank = inverse(<tex>A_{S_{12}}</tex>)
'''while''' i < 2 * n / 3 '''and''' j < n / 3:
pos12 = <tex> A_{S_{12}} </tex>[i]
pos0 = <tex> A_{0} </tex>[j]
<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])
j++
