Изменения

Для выяснения общего префикса строк, автор предлагает находить общего предка вершин в [[Сжатое суффиксное дерево|суффиксном дереве]] и считает, что такой предок можно найти за константное время. Для примера в этом дереве, общее начало строк '''5''' и '''9''' (<tex>11011111000</tex> и <tex>1111011111000</tex>) записано в пути от корня до общего предка этих вершин: (рис. рисунок 3-1)

[[Файл:treestep3_blue.jpg|400px|рис. рисунок 3-1]]

Поскольку структуры нечётного дерева у нас заранее нет и мы её только строим, то подходящих предков мы можем найти в исходном чётном дереве, для этого достаточно проверить вершины с номерами на еденицу меньше и отрезать первый символ : (рис. рисунок 3-2).

[[Файл:treestep3_red.jpg|400px|рис. рисунок 3-2]]