Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура для поиска подстроки в строке, но занимающая много места в памяти. Рассмотрим все такие пути от <tex>u</tex> до <tex>v</tex> в суффиксном боре, в которых каждая вершина имеет только одного сына. Такие пути Такой путь можно сжать до одного ребра <tex>u v</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>|\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</tex> листьями, удовлетворяющее условию леммы по индукционному предположению, причем в нем количество внутренних вершин равно количеству внутренних вершин в исходном дереве. Тогда у полученного дерева менее <tex>n</tex> внутренних вершин, значит в исходном дереве количество внутренних вершин так же меньше количества листьев.

Очевидно, суффиксное дерево в виде массива занимает <tex>O(|V||\Sigma|)</tex> памяти. Так как любое суффиксное дерево удовлетворяет условиям леммы, и все его внутренние (у каждой вершины, по определению, имеют не менее двух детей), то количество внутренних вершин в нем меньше количества листьев, равного <tex>n</tex>. Значит, поэтому для его хранения требуется <tex>O(n|\Sigma|)</tex> памяти.

insert(l,r) //процедура вставки

'''if''' <tex>s[i+j-start] <>s[j] </tex> //если нашли не совпадающий символ

==Использованиесжатого суффиксного дерева==