Изменения

Перейти к: навигация, поиск

Сжатое суффиксное дерево

248 байт добавлено, 19:21, 24 апреля 2016
Наивный алгоритм
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
  go[0] = '''newstruct''' Vertex: <span style="color:Green">// Vertex - функцияСтруктура, возвращающая корень деревасодержащая информацию о вершине </span> l <span style="color:Green">// левый потомок </span> r <span style="color:Green">// правый потомок </span> v <span style="color:Green">// номер вершины </span>   go[0] = '''new''' Vertex
count = 0 <span style="color:Green">// номер последней вершины, созданной в дереве (глобальная переменная)</span>
'''for''' i = 0 '''to''' n <span style="color:Green">// для каждого символа строки</span>
313
правок

Навигация