Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она требует порядка квадрата длины исходной строки памяти. Оптимизацией суффиксного бора, требующей линейное количество памяти, является '''сжатое суффиксное дерево'''(англ. ''compressed suffix tree''), рассматриваемое далее.

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

Количество Число внутренних вершин дерева, каждая из которых имеет не менее двух детей, меньше количества числа листьев.

'''Переход''' : При <tex>n \rightarrow n + 1= 2</tex>в дереве одна внутренняя вершина, следовательно утверждение верно.

Возьмем вершину в дереве с : '''Переход''' <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>|V| \times |\Sigma|</tex>, где <tex>|V|</tex> {{---}} количество число вершин в дереве, <tex>|\Sigma|</tex> {{---}} мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины, по определению, не менее двух детей), значит, <tex>|V| = O(2 n)</tex>. Каждая <tex>a[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет ребро из <tex>i</tex>-ой вершины по <tex>j</tex>-ому символу и индексы <tex>l, r</tex> начала и конца подстроки, записанной на данном переходе. Итак, дерево занимает <tex>O(n|\Sigma|)</tex> памяти.

  go[0] '''struct''' Vertex: <span style="color:Green">// Структура, содержащая информацию о вершине </span> '''int''' l <span style="color:Green">// индекс начала подстроки </span> '''int''' r <span style= Vertex() "color:Green">// индекс конца подстроки </span> '''int''' v <span style="color:Green">// кореньиндекс текущей позиции </span> go[0] = '''new''' Vertex

'''if''' (go[cur][s[l]].v == -1) <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span>

go[++count] = '''new''' Vertex()

В вершинах дерева <tex>Node</tex> мы будем хранить предка <tex>\mathtt {parent}</tex>, [[Стек| стек]] детей в лексикографическом порядке ребер <tex>\mathtt{children}</tex>, глубину вершины в символах от корня <tex>\mathtt{depth}</tex>.

'''Node ''' addNextSuffix('''Node ''' previous, '''int''' length, '''int''' lcp):

added = '''Node'''(previous, length)

'''if''' previous.parent.depth < lcp: <font color=green> // Нужно разрезать ребро </font> inserted = '''Node'''(prevous.parent, lcp)

'''Node ''' buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length): root = '''Node'''('''null''', 0)

В процессе построения мы нигде не запоминали сами позиции строки, соответствующие ребрам. Чтобы их восстановить, достаточно определить максимальный суффикс, который проходит по этому ребру. Для этого с помощью [[Обход в глубину, цвета вершин| обхода в глубину]] посчитаем для каждой вершину дерева максимальную глубину ее листа <tex>\mathtt{maxDepth}</tex>.

'''functionvoid''' calculatePositions('''Node ''' parent, '''Node ''' child, '''int''' stringLength):

Пусть длина строки <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> символов.

'''Node ''' minNode = root

'''functionvoid''' dfs('''Node ''' n):

Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи [[Обход в глубину, цвета вершин| обхода в глубину]]. Начиная с корня, спускаясь вниз, для листов левый символ уже известен {{---}} при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины <tex>v</tex> запустим проверку. :*если '''Случай 1.''' Если среди левых детей <tex>v</tex> есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем <tex>v</tex> как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>v</tex> начинаются с одного и того же символа),. *если :'''Случай 2.''' Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей. ::**если '''Случай 2.1.''' Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в <tex>v</tex> этот символ <tex>x</tex>,. **если ::'''Случай 2.2.''' Если не все левые символы детей <tex>v</tex> эквивалентны, то записываем в <tex>v</tex>, что она различна влево.