Изменения
в условии "=" заменено на "=="
Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше числа листьев.
|proof=
: '''Переход''' <tex>n \rightarrow n + 1</tex> : Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{---}} листья. Рассмотрим возможные случаи:
# У нее более двух детей. Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, причем в нем число внутренних вершин такое же, как в исходном дереве. Но у полученного дерева по индукционному предположению менее <tex>n</tex> внутренних вершин, а, значит, и для исходного дерева лемма верна.
# У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n - 1</tex> листьями, число внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n - 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n+ 1</tex>.
}}
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
count = 0 <span style="color:Green">// номер последней вершины, созданной в дереве (глобальная переменная)</span>
'''for''' i = 0 '''to''' n <span style="color:Green">// для каждого символа строки</span>
cur = 0
'''while''' (l < r)
'''if''' (go[cur][s[l]].v == -1) <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>
createVertex(cur, l, r) <span style="color:Green">// создаем новую вершину</span>
'''else'''
'''void''' createVertex('''int''' cur, '''int''' l, '''int''' r):
go[++count] = '''new''' Vertex()
go[cur][s[l]].v = count
go[cur][s[l]].l = l
go[cur][s[l]].r = r
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.
# Вставить новую вершину как сына вершины с глубиной <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>
'''Node ''' addNextSuffix('''Node ''' previous, '''int''' length, '''int''' lcp):
'''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)
'''Node ''' buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length): root = '''Node'''('''null''', 0)
previous = root
'''for''' i = 1 '''to''' length
</code>
В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.
Тогда ребро <tex>s[start, end]</tex> определяется так:
<code>
'''functionvoid''' calculatePositions('''Node ''' parent, '''Node ''' child, '''int''' stringLength):
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
Тогда суффиксный массив строится из суффиксного дерева [[Обход в глубину, цвета вершин| обходом в глубину]] в указанном порядке.
Пусть длина строки <tex>\mathtt{length}</tex>, глубина листа в символах <tex>\mathtt{depth}</tex>, тогда номер суффикса <tex>\mathtt{i = length - depth}</tex>.
Для заполнения массива <tex>lcp</tex> нам понадобится вершина <tex>\mathtt{minNode}</tex>, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет [[Сведение задачи LCA к задаче RMQ| наименьший общий предок]] этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно <tex>\mathtt{lcp = minNode.depth}</tex> символов.
<code>
'''int''' curPos = 0
'''Node ''' minNode = root
<font color=green>// Для заполнения нужно вызвать dfs(root) </font>
'''functionvoid''' dfs('''Node ''' n):
'''if''' n.children.size == 0
suf[curPos] = length - n.depth
