Изменения

В этом преобразовании используется тот же инвариант, что и в других суффиксных структурах:

# Строка <tex>s</tex> заканчивается специальным символом, который больше не встречается в строке.

Будем строить дерево, добавляя суффиксы в лексикографическом порядке. Чтобы ускорить добавление, будем использовать то, что <tex>i</tex>-ый суффикс имеет с предыдущим <tex>lcp[i]</tex> общих символов. Тогда добавление из корня не отличается от того, что мы поднимемся вверх из предыдущего суффикса до глубины <tex>lcp[i]</tex> и продолжим построение оттуда. Инвариант позволяет нам утверждать, что ни один лист мы не сможем продолжить, и нам всегда нужно будет хоть раз подняться из него вверх. Поскольку суффиксы отсортированы лексикографически, мы не будем спускаться по ребру после того, как уже поднялись из него из-за несовпадения символа. Все это позволяет сформулировать алгоритм добавления суффикса по известной вершине предыдущего суффикса:

'''if''' previous.depth == 0 '''or''' previous.depth == lcp: <font color=green> // Добавляем к сыновьям текущей вершины </font>

added = Node(previous, length)

'''return''' added

'''else:'''

'''if''' previous.parent.depth < lcp: <font color=green> // Нужно разрезать ребро </font>

inserted = Node(prevous.parent, lcp)

previous.parent = inserted

'''return''' addNextSuffix(previous.parent, length, lcp)

<font color=green>// Для заполнения нужно вызвать dfs(root) </font>

'''function''' dfs(Node n):

suf[curPos] = length - n.depth

lcp[curPos] = minNode.depth