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