497
правок
Изменения
→Шаг 3: построение нечетного по четному
Для выяснения общего префикса строк, автор предлагает использовать находить общего предка вершин в суффиксном дереве. Считается что такой предок можно найти за константное время. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (11011111000 1111011111000) записано в пути от корня до общего предка этих вершин: (рис. 3-1)
[[Файл:treestep3_redtreestep3_blue.jpg|400px|thumb|left|рис. 3-21]]
Поскольку структуры нечётного дерева у нас заранее нет и мы её только строим, то подходящих предков мы можем найти в исходном чётном дереве, для этого достаточно проверить вершины с номерами на еденицу меньше и отрезать первый символ : (рис. 3-2).
[[Файл:treestep3_red.jpg|400px|рис. 3-2]]
== Шаг 4: слияние четного и нечетного дерева ==
