Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура для поиска подстроки в строке, но занимающая много места в памяти. Рассмотрим все такие пути от <tex>u</tex> до <tex>v</tex> в суффиксном боре, в которых каждая вершина имеет только одного сына. Такие пути можно сжать до одного ребра <tex>u v</tex>, пометив его всеми встречающимися на пути символами. Получившееся дерево носит название '''сжатое суффиксное дерево'''. ==Определение=='''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} ориентированное дерево , с корнем, имеющее ровно <tex>n</tex> листьевлистами, занумерованных от <tex>1</tex> до <tex>n</tex>. Каждая каждая внутренняя вершинакоторого, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена каждое ребро помечено непустой подстрокой строки <tex>s</tex>и символом, с которого начинается эта подстрока. Никакие две дугидва ребра, выходящие из одной и той же вершины, не могут иметь одинаковых символьных пометок, начинающихся с одного и того же символа. Суффиксное дерево содержит все суффиксы строки <tex>s</tex>: для каждого листа <tex>i</tex> конкатенация меток дуг подстрок на ребрах пути от корня к листу <tex>i</tex> в точности составляет суффикс, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..n]</tex>.

Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>. Во избежание этого в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило, защитный символ обозначается <tex>\$</tex>. Любой суффикс строки с защитным символом заканчивается в листе, т.к. этот символ не встречается в строке нигде, кроме позиции последнего символа. ==Хранение суффиксного дерева==Как уже было отмечено выше, каждое ребро дерева помечается подстрокой исходной строки <tex>s</tex>. Значит, можно для каждого ребра хранить не саму подстроку, а индексы начала и конца подстроки в исходной строке {{---}} <tex>l, r</tex>. Итак, с каждым ребром дерева ассоциируются две инцидентные ей вершины, символ, с которого начинается подстрока на ребре и два числа <tex>l, r</tex>. Представим его как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве. Каждая <tex>[i][j]</tex> ячейка массива содержит информацию о том, в какую вершину ведет <tex>i-ое</tex> ребро по <tex>j-ому</tex> символу, в какую вершину оно ведет и индексы <tex>l, r</tex> подстроки на ребре.

==Связь с суффиксным боромКоличество вершин==Пусть В сжатом суффиксном дереве содержится <tex>Pn</tex> {{---}} [[Суффиксный бор|суффиксный бор]] листьев, т.к. каждый суффикс строки <tex>s</tex>заканчивается в листе. Тогда сжатое суффиксное дерево <tex>T</tex> может быть получено из <tex>P</tex> слиянием каждого пути из неветвящихся Рассмотрим теперь количество внутренних вершин в одну дугутакого дерева.

Рассмотрим все вершиныв дереве для строки длины <tex>n + 1</tex>, у которых хотя бы один из детей - лист.

Если среди них есть вершина, у которой более двух детей, отрежем от нее лист. Получим дерево с <tex>n</tex> листьями, удовлетворяющее условию леммыпо индукционному предположению, причем в котором нем количество внутренних вершин равно количеству внутренних вершин в исходном дереве. Тогда, по индукционному предположению, у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин так же меньше количества листьев.

==Хранение в памятиЗанимаемая память==Очевидно, суффиксное дерево в виде массива занимает <tex>O(|V||\Sigma|)</tex> памяти. Так как любое суффиксное дерево удовлетворяет условиям леммы, то количество внутренних вершин в нем меньше количества листьев, равного <tex>n</tex>, поэтому для его хранения требуется <tex>O(n|\Sigma|)</tex> памяти. ==Построение суффиксного дерева==Рассмотрим наивный алгоритм построения суффиксного дерева. Этот алгоритм работает за время<tex>O(n^2)</tex>, однако существует [[Алгоритм Укконена| алгоритм Укконена]], позволяющий построить дерево за время<tex>O(n)</tex>.

* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix)исходной строки