275
правок
Изменения
→Реализация алгоритма за O(n)
'''Node''' root = new Node(0, 0, 0, null)
'''Node''' node = root <font color=green>// вершина, в которой мы остановились на предыдущем шаге текущей итерации</font>
'''int''' tail = 0 <font color=green>// длина в символах количество символов до конца максимального не уникального текущего суффиксапо метке, которой помечено ребро, ведущее в node</font>
'''for''' i = 0..n
node = ch
ch = ch.children[s[i - tail]]
'''if''' ch == null <font color=green>// используем правило создаем новую вершину по правилу продления 2.1</font> node.children[а с ребром, помеченным s[i]] = new Node(i, n, node)
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
'''else'''
t = s[ch.begin + tail]
'''if''' t == s[i] <font color=green>// используем правило ничего не делаем по правилу продления 3</font>
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
'''break'''
'''else''' <font color=green>// используем правило продления 2.2</font>б : '''Node''' splitNode = new Node(ch.beginразделяем ребро, ch.begin + tailведущее в текущую вершину, node)новой вершиной splitNode splitNode.children[s[i]] = new Node(i, nи создаем новый лист с ребром, splitNode) splitNode.children[t] = ch ch.begin += tail ch.parent = splitNode node.children[помеченным s[i - tail]] = splitNode
'''if''' last <tex>\ne</tex> null
last.suffixLink = splitNode
