80
правок
Изменения
→Построение суффиксного дерева
==Построение суффиксного дерева==
Рассмотрим наивный алгоритм построения суффиксного дерева:
<tex>count \leftarrow 0</tex> //номер последней вершины, созданной в дереве (глобальная переменная)
'''for''' <tex> i \leftarrow 0 </tex> '''to''' <tex> n </tex> '''do''' //для каждого символа строки
insert(<tex>i, n</tex>) //добавляем суффикс, начинающийся с него
insert(l,r)
<tex> cur \leftarrow root </tex>
'''while''' (<tex> i l < r </tex>) '''if''' <tex> go[cur][s[i]].v = 0 </tex> //если мы не можем пойти из вершины по символу <tex> i l </tex> create_vertexcreateVertex(<tex>cur, new V, l, r</tex>) //создаем новую вершину
'''else'''
<tex>start \leftarrow go[cur][s[i]].l </tex>
<tex>finish \leftarrow go[cur][s[i]].r </tex>
<tex>hasBreak \leftarrow false </tex>
'''for''' <tex> j = start </tex> '''to''' <tex> finish </tex> //для каждого символа на ребре из текущей вершины
'''if''' <tex>s[i+j-start] <>s[j] </tex> //если нашли не совпадающий символ
'''break'''
'''if''' '''ребро не разбивали'''<tex>!hasBreak</tex>
<tex>cur \leftarrow go[cur][s[i]].v </tex> //переходим по ребру
<tex>i l \leftarrow i l + finish - start </tex> //двигаемся по суффиксу на длину подстроки, записанной на ребре createVertex(<tex>cur, l, r</tex>) <tex>go[cur][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> newEdge(<tex>cur, i, j, r</tex>) <tex>next \leftarrow go[cur][s[l]].v</tex> createVertex(<tex>cur, l, j - 1</tex>) <tex>cur \leftarrow go[cur][s[l]].v</tex> createVertex(<tex>cur, j, r</tex>) <tex>go[cur][s[j]].v \leftarrow next </tex> <tex>go[cur][s[j]].l \leftarrow j </tex> <tex>go[cur][s[j]].r \leftarrow r </tex>
Этот алгоритм работает за время <tex>O(n^2)</tex>, однако [[Алгоритм Укконена| алгоритм Укконена]] позволяет построить сжатое суффиксное дерево за <tex>O(n)</tex>.
