497
правок
Изменения
Нет описания правки
* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:
[[Файл:tree101232.png|300px|суффиксное дерево для сжатой строки]]
'''суффиксное дерево для сжатой строки'''* рекурсия не продолжается, если строка имеет длину <tex>1</tex>: возвращается суффиксное дерево из одной вершиныстроится тривиально.
=== Шаг 2: построение чётного дерева ===
Номер каждой пары превращается в номер четного суффикса исходной строки. Раскрываем все пары в суффиксы, а номера в листьях от этого умножатся на <tex>2</tex> очевидным образом:
[[Файл:Tree101232even-pre.png|300px|Очевидно, что для этого достаточно умножить Раскрываем все расстояния пары в дереве на 2суффиксы]]'''дерево с раскрытыми парами в суффиксы'''
Корректируются все развилки дерева (так как они могут совпадать в первых символах):
[[Файл:Tree101232even.png|300px|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
'''все развилки скорректированы'''
Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex>
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях).
* [[Сжатое_суффиксное_дерево#.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 | Строим по чётному дереву суффиксный массив]] — это можно сделать за <tex>О(n)</tex>.
* Дописываем ко всем суффиксам кроме того, что на нулевой позиции символ, предшествующий ему в строке.
* Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс, которые . А чётные суффиксы у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.* [[Сжатое_суффиксное_дерево#.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.png|thmb|450px|Слитое дерево (условно)]]
