497
правок
Изменения
→Шаг 3: построение нечетного по четному
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях).
По лексикографическому обходу листьев дерева и по известным днинам длинам наибольшего общего префикса двух соседних листьев можно легко восстановить дерево.
Мы хотим получить лексикографически отсортированные нечетные суффиксы строки. Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже отсортированы. Тогда поразрядно отсортируем их за линейное время.
