497
правок
Изменения
→шаг 1: построение четного дерева
которого ограничены нечетными позициями <tex>2,4,6,{...} </tex> строки <tex>s\$</tex>.}}
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное потому в нём будут только половина суффиксов, т.е. тех которые стоят в чётных позициях. :
[[Файл:Tree101232even-pre.png|300px|thumb|left|Очевидно, что для этого достаточно умножить все расстояния в дереве на 2]]
[[Файл:Tree101232even.png|300px|thumb|center|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
{|class="wikitable"
|+
!width="20%"|ID !!width="20%"|LCP !!width="20%"|STR
|- align = "center"
|2
|0
|1112212221
|- align = "center"
|0
|1
|121112212221
|- align = "center"
|4
|2
|12212221
|- align = "center"
|6
|0
|212221
|- align = "center"
|10
|2
|21
|- align = "center"
|8
|1
|2221
|}
== шаг 2: построение нечетного по четному ==
