74
правки
Изменения
м
→Алгоритм Карккайнена-Сандерса
* '''Суффиксный массив для позиций не кратных 3'''
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | \mid i \bmod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.
* '''Суффиксный массив для позиций кратных 3'''
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | \mid i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | \mid i \bmod 3 = 0 \} </tex>, где <tex> S[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:
<tex>A_{S_0}</tex> = []
|style="background-color:#FFF;padding:2px 30px"| <tex> cab\$\$ </tex>
|}
Заметим, что №9 № 9 будет выброшен, так как в начале алгоритма был добавлен один <tex> \$ </tex> к строке
{|
