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