80
правок
Изменения
→Построение суффиксного дерева
<tex> cur \leftarrow root </tex>
'''while''' (<tex> l < r </tex>)
'''if''' <tex> go[cur][s[il]].v = 0 </tex> //если мы не можем пойти из вершины по символу <tex> l </tex>
createVertex(<tex>cur, l, r</tex>) //создаем новую вершину
'''else'''
<tex>start \leftarrow go[cur][s[il]].l </tex> <tex>finish \leftarrow go[cur][s[il]].r </tex>
<tex>hasBreak \leftarrow false </tex>
'''for''' <tex> j = start </tex> '''to''' <tex> finish </tex> //для каждого символа на ребре из текущей вершины
'''if''' <tex>s[il+j-start] <>s[j] </tex> //если нашли не совпадающий символ
newEdge(<tex>cur, l, j, r</tex>) //создаем вершину на ребре
<tex>hasBreak \leftarrow true </tex>
'''break'''
'''if''' <tex>!hasBreak</tex>
<tex>cur \leftarrow go[cur][s[il]].v </tex> //переходим по ребру
<tex>l \leftarrow l + finish - start </tex> //двигаемся по суффиксу на длину подстроки, записанной на ребре
