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