497
правок
Изменения
→Шаг 3: построение нечетного по четному
которого ограничены нечетными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Мы хотим получить лексикографически отсортированные нечетные суффиксы строки, По лексикографическому обходу листьев дерева и по которым восстановим нечетное известным днинам наибольшего общего префикса двух соседних листьев можно легко восстановить дерево. Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже отсортированы. Тогда поразрядно отсортируем их за линейное время. Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.
Мы хотим получить лексикографически отсортированные нечетные суффиксы строки. Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже отсортированы. Тогда поразрядно отсортируем их за линейное время.
Для выяснение общего префикса строк можно находить общего предка вершин в [[Сжатое суффиксное дерево|суффиксном дереве]]. Такого предка можно найти за [http://e-maxx.ru/algo/lca_linear константное время, потратив <tex>O(n)</tex> на препроцессинг]. Для примера в этом дереве, общее начало строк '''5''' и '''3''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рисунок 3-1)
[[Файл:treestep3_red.jpg|400px|рисунок 3-2]]
Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.
=== Шаг 4: слияние четного и нечетного дерева ===
