497
правок
Изменения
Нет описания правки
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях).
* [[ Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Строим по чётному дереву суффиксный массив]] — это можно сделать за О(n).
* Дописываем ко всем суффиксам кроме того, что на нулевой позиции символ, предшествующий ему в строке.
* Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построить из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.
[[Файл: Odd.jpgpng|thmb|450px|Слитое дерево (условно)]]
Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.
