497
правок
Изменения
→Шаг 2: построение четного дерева
|}
=== Шаг 2: построение четного чётного дерева ===
{{Определение
|definition= Четное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья
которого ограничены нечетными позициями <tex>2,4,6, \dots </tex> строки <tex>s\$</tex>.}}
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное оно потому, что в нём будет только половина суффиксов, то есть те, которые стоят в чётных позициях: .
[[Файл:Tree101232even-pre.png|300px|thumbОчевидно, что для этого достаточно умножить все расстояния в дереве на 2]] Корректируются все развилки дерева (так как они могут совпадать в первых символах): [[Файл:Tree101232even.png|center300px|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
{|class="wikitable"
