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