313
правок
Изменения
→Наивный алгоритм
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
go[0] = Vertex() <span style="color:Green">// корень</span> count = 0 <span style="color:Green">// номер последней вершины, созданной в дереве (глобальная переменная)</span> '''for''' i = 0 '''to''' n <span style="color:Green">// для каждого символа строки</span> insert(i, n) <span style="color:Green">// добавляем суффикс, начинающийся с него</span>
'''void''' insert('''int''' l, '''int''' r):
cur = 0
'''while''' l < r
'''if''' go[cur][s[l]].v == -1 <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span> createVertex(cur, l, r) <span style="color:Green">// создаем новую вершину </span>
'''else'''
start = go[cur][s[l]].l
finish = go[cur][s[l]].r
hasCut = ''false'' '''for''' j = start '''to''' finish <span style="color:Green">// для каждого символа на ребре из текущей вершины</span> '''if''' s[l+j-start] <tex> \neq </tex> != s[j] <span style="color:Green">// если нашли не совпадающий символ</span> <span style="color:Green">// создаем вершину на ребре</span>
old = go[cur][s[l]]
createVertex(cur, l, j - 1)
go[count][s[j]].l = finish
createVertex(count, l + j - start, r)
hasCut = ''true''
'''break'''
'''if''' !hasCut
cur = go[cur][s[l]].v <span style="color:Green">// переходим по ребру</span> l = l + finish - start <span style="color:Green">// двигаемся по суффиксу на длину подстроки, записанной на ребре</span>
'''else'''
'''break'''
'''void''' createVertex('''int''' cur, '''int''' l, '''int''' r):
go[++count] = Vertex()
go[cur][s[l]].v = count
