Изменения
→Построение из суффиксного массива: небольшие правки
# (Следствие) <tex>lcp[i] < len[i - 1]</tex>, где <tex>len[i - 1]</tex> {{---}} длина суффикса, соответствующего <tex>suf[i - 1]</tex>.
В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>parent</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>children</tex>, глубину вершины в символах от корня <tex>depth</tex>. Соответственно, конструктор вершины имеет вид <code>Node(Node parent, '''int''' depth)</code>.
Будем добавлять суффиксы в лексикографическом порядке, заданном суффиксным массивом <tex>suf</tex>. Также будем и запоминать последнюю добавленную вершину <tex>previous</tex>. Тогда каждый <tex>i</tex>-ый добавленный суффикс будет иметь с предыдущим <tex>lcp[i]</tex> общих символов, что позволит ускорить добавление. Алгоритм добавления суффикса:# Если мы находимся в корне, либо <tex>depth = lcp</tex>, новый суффикс нужно добавить к детям.# Если <tex>parent.depth < lcp</tex>, новый суффикс будет идти из середины ребра к предку. Вставим между нами и будет использоваться для быстрого добавленияпредком вершину с глубиной <tex>lcp</tex>.# Вызовем добавление суффикса у нашего предка.
<code>
'''if''' previous.depth == 0 '''or''' previous.depth == lcp <font color=green> // Добавляем к сыновьям текущей вершины </font>
added = '''Node'''(previous, length)
previous.children.'''push'''(added)
'''return''' added
'''else'''
'''if''' previous.parent.depth < lcp <font color=green> // Нужно разрезать ребро </font>
inserted = '''Node'''(prevous.parent, lcp)
previous.parent.children.'''pop'''()
previous.parent.children.'''push'''(inserted)
'''return''' addNextSuffix(previous.parent, length, lcp)
previous = root
'''for''' i = 1 '''to''' length
<code>
calculatePositions('''Node''' parent, '''Node''' child, '''int''' stringLength)
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
Для асимптотического анализа будем использовать в качестве [[Амортизационный анализ#Метод потенциалов| потенциала]] глубину в вершинах. При добавлении суффикса мы спускаемся один раз, подняться выше корня мы не можем, значит и подниматься мы будем суммарно <tex>O(n)</tex> раз. Обход в глубину также выполняется за <tex>O(n)</tex>, итоговая асимптотика <tex>O(n)</tex>.
Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое. Это говорит об эквивалентности этих структур, и мы можем выбирать нужное представление исходя из требуемых свойств.
==Использование сжатого суффиксного дерева==
