Изменения
→Шаг 2
=== Шаг 2 ===
На этом шаге мы за линейное время получим суффиксный массив <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.
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:
Получили, что весь второй шаг требует <tex> O(n) </tex> времени.
=== Шаг 3 ===
