Далее <tex>n</tex> - длина строки <tex>s</tex> с защитным символом.
==Хранение суффиксного дерева==
Заметим, что для хранения на ребре подстроки используют индексы <tex>l, r</tex> ее начала и конца в исходной строке и не хранят саму строку. Теперь представим дерево как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> - мощность алфавита. Каждая <tex>[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex>. Такое дерево занимает <tex>O(|V||\Sigma|)</tex> памяти.
==Количество вершин==
В сжатом По определению, в суффиксном дереве содержится <tex>n</tex> листьев, т.к. строка <tex>s</tex> содержит ровно <tex>n</tex> суффиксов. Рассмотрим теперь количество внутренних вершин такого дерева.
{{Лемма
'''Переход''' <tex>n \rightarrow n + 1</tex>
Рассмотрим все вершины вершину в дереве для строки длины с <tex>n + 1</tex>листами, у которых хотя бы один из детей которой два ребенка - листлистья.
Если среди них есть вершина, у которой 1) У нее более двух детей, . Тогда отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы по индукционному предположению, причем в нем количество внутренних вершин равно количеству внутренних вершин такое же, как в исходном дереве. Тогда Но у полученного дерева менее <tex>n</tex> внутренних вершин(т.к. по индукционному предположению для него выполняется условие леммы), значит в исходном дереве количество внутренних вершин меньше количества листьев, для исходного дерева лемма верна.
Иначе среди этих вершин есть вершина, у которой оба 2) У нее ровно два ребенка - листья. Отрежем оба этих листаих, получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммы, количество внутренних вершин которого на <tex>1</tex> меньше количества внутренних вершин , чем в исходном дереве. Тогда, по индукционному предположению, у полученного дерева него менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин их меньше <tex>n + 1</tex>.
}}
==Занимаемая память==
Так Заметим, что для хранения на ребре подстроки используют индексы <tex>l, r</tex> ее начала и конца в исходной строке, а не хранят саму строку. Представим теперь дерево как любое суффиксное дерево удовлетворяет условиям леммы массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> - мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины по определению не менее двух детей), то количество внутренних вершин в нем меньше количества листьевзначит, равного <tex>|V| = O(2*n)</tex>. Каждая <tex>[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex>. ЗначитИтак, для его хранения требуется дерево занимает <tex>O(n*|\Sigma|)</tex> памяти.
==Построение суффиксного дерева==
insert(l,r)
<tex> cur \leftarrow root </tex> //инициализируем текущую вершину корнем
'''while''' (<tex> i < r </tex>)
'''if''' <tex> go[cur][s[i]].v = 0 </tex> //если мы не можем пойти из вершины по символу <tex> i </tex>
<tex>i \leftarrow i + finish - start </tex> //двигаемся по суффиксу на длину подстроки, записанной на ребре
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако существует [[Алгоритм Укконена| алгоритм Укконена]], позволяющий позволяет построить сжатое суффиксное дерево за время <tex>O(n)</tex>.
==Использование сжатого суффиксного дерева==
