1679
правок
Изменения
Нет описания правки
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_o} </tex> для суффиксов строки, начинающихся в нечетных позициях, используя уже построенный <tex> A_{S_e} </tex>.
Заметим, что сортировка множества нечетных суффиксов <tex> \{ S[i..n] | i \mod 2 == 1 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \mod 2 == 1 \} </tex>. Однако <tex> S[i+1..n] </tex> — четный суффикс, и его относительную позицию мы уже узнали на шаге 1, то есть свели задачу к сортировке <tex> \{ (S[i], pos_e[i+1]) | i \mod 2 == 1 \} </tex>, где <tex> pos_e[i] </tex> — позиция суффикса <tex> S[i..n] </tex> в <tex>A_{S_e} </tex>.
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_e} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара <tex> (S[n-1], n) </tex>. Псевдокод этого шага:
M.add(Pair(S[<tex> A_{S_e}[i] </tex>-1], <tex> A_{S_e}[i]</tex>))
Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементами хранит не суффиксы, а их позиции в строке <tex> S </tex>, но главное — что он отсортирован по возрастанию соответствующих вторым элементам суффиксамэтих суффиксов. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_o} </tex>:
<tex> A_{S_o} </tex> = []
for i = 0..n/2 - 1:
