322
правки
Изменения
м
→Шаг 2
M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))
Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементам и хранит не суффиксы, а их позиции в строке <tex> S </tex>, но главное — что он отсортирован по возрастанию соответствующих этим позициям нечетным суффиксамнечетных суффиксов. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_e} </tex>:
stable_sort(M)
<tex> A_{S_e} </tex> = []
