Изменения
→Построение из суффиксного массива
# Вставить новую вершину как сына вершины с глубиной <tex>lcp</tex>.
В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>\mathtt{depth}</tex>.
Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.
</code>
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.
Тогда ребро <tex>s[start, end]</tex> определяется так:
