Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она занимает много места в требует порядка квадрата длины исходной строки памяти. Рассмотрим в боре все пути от <tex>u</tex> до <tex>v</tex>Оптимизацией суффиксного бора, в которых у каждой вершины только один сын. Такой путь можно сжать до ребра <tex>u v</tex>, записав на нем все встречающиеся на пути символытребующей линейное количество памяти, которые являются подстрокой исходной строки. Для хранения ее на ребре обычно используют индексы <tex>l, r</tex> начала и конца. Получилось является '''сжатое суффиксное дерево'''рассматриваемое далее.

'''Данное определение порождает следующую проблему:''' <br/>Рассмотрим дерево для строки <tex>xabxa</tex>. У него : суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, а, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Как правило, это Обозначим его как <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе, т. к. в такой строке не существует двух различных подстрок одинаковой длины, заканчивающихся на <tex>\$</tex>.

Далее <tex>n</tex> {{- --}} длина строки <tex>s</tex> с защитным символом.

По определению, в суффиксном дереве содержится <tex>n</tex> листьев. Рассмотрим Оценим количество внутренних вершин такого дерева.

При <tex>n = 2</tex> в дереве одна внутренняя вершина - , следовательно утверждение верно.

Возьмем вершину в дереве с <tex>n + 1</tex> листами, у которой два ребенка {{- --}} листья. Рассмотрим возможные случаи:

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

2) У нее ровно два ребенка. Отрежем их, получим дерево с <tex>n- 1</tex> листьями, количество внутренних вершин которого на <tex>1</tex> меньше, чем в исходном дереве. Тогда по индукционному предположению у него менее <tex>n- 1</tex> внутренних вершин, значит, в исходном дереве их меньше <tex>n + 1</tex>.

Представим дерево как двумерный массив размера <tex>[|V|*\times |\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> памяти.

Рассмотрим наивный алгоритм построения суффиксного дерева: строки <tex>count \leftarrow 0s</tex> : go[0] = new Vertex() //корень count = 0 //номер последней вершины, созданной в дереве (глобальная переменная) '''for''' <tex> i \leftarrow = 0 </tex> '''to''' <tex> n </tex> '''do''' //для каждого символа строки insert(<tex>i, n</tex>) //добавляем суффикс, начинающийся с него

<tex> cur \leftarrow root </tex>= 0 '''while''' (<tex> l < r </tex>) '''if''' <tex> go[cur][s[l]].v = 0 </tex> = -1 '''then''' //если мы не можем пойти из вершины по символу <tex> l </tex> createVertex(<tex>cur, l, r</tex>) //создаем новую вершину '''else''' <tex> start \leftarrow = go[cur][s[l]].l </tex> <tex> finish \leftarrow = go[cur][s[l]].r </tex> <tex> hasCut \leftarrow = false </tex> '''for''' <tex> j = start </tex> '''to''' <tex> finish </tex> //для каждого символа на ребре из текущей вершины '''if''' <tex>s[l+j-start] <>s[j] </tex> '''then''' //если нашли не совпадающий символ '''cutEdge()''' //создаем вершину на ребре <tex> old = go[cur][s[l]] createVertex(cur, l, j - 1) go[count][s[j]].v = old go[count][s[j]].r = j go[count][s[j]].l = finish createVertex(count, l + j - start, r) hasCut \leftarrow = true </tex> '''break''' '''if''' <tex>!hasCut</tex>'''then''' <tex> cur \leftarrow = go[cur][s[l]].v </tex> //переходим по ребру <tex> l \leftarrow = l + finish - start </tex> //двигаемся по суффиксу на длину подстроки, записанной на ребре '''else''' '''break'''

createVertex(<tex>cur, l, r</tex>) <tex>go[cur++count][s[l]] \leftarrow = new Vertex()</tex> <tex>go[cur][s[l]].v \leftarrow = count</tex> <tex>go[cur][s[l]].l \leftarrow = l</tex> <tex>go[cur][s[l]].r \leftarrow = r</tex> <tex>count++</tex>