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