120
правок
Изменения
Добавлен псевдокод
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..n], j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..n]</tex>. Тогда и <tex>s[i..n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
}}
== Псевдокод ==
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
* <tex>parent</tex> - предок;
* <tex>start, end</tex> - позиции строки, соответствующие ребру до предка;
* <tex>length</tex> - длина ребра до предка
* <tex>depth</tex> - глубина вершины в символах;
* <tex>suf</tex> - суффиксная ссылка;
* <tex>children[]</tex> - массив детей.
Конструктор будет иметь вид <code>Node(Node parent, '''int''' start, '''int''' end, '''int''' depth)</code>
<code>
'''string''' s
'''int''' n = s.length
Node buildSuffixTree()
superRoot = Node('''null''', 0, -1, 0)
root = Node(superRoot, 0, -1, 0)
root.suf = superRoot
'''for''' c '''in''' <tex>\Sigma</tex>
superRoot.children[c] = root
head = root
'''for''' i = 1 '''to''' n
head = addSuffix(head, i)
'''return''' root
Node addSuffix(Node head, '''int''' start)
newHead = slowScan(fastScan(head), start)
newLeaf = Node(newHead, start + newHead.depth, n, n - start + 1)
newHead.children[s[start + newHead.depth]] = newLeaf
'''return''' newHead
Node fastScan(Node head)
'''if''' head.suf == '''null'''
skipped = head.length
curPos = head.start
curNode = head.parent.suf
'''while''' curNode.children[s[curPos]].length >= skipped
curNode = curNode.children[s[curPos]]
skipped -= curNode.length
curPos += curNode.length
'''if''' skipped > 0
newNode = split(curNode, curNode.children[s[curPos]], skipped)
head.suf = newNode
'''return''' head.suf
Node split(Node parent, Node child, '''int''' edgeLength)
newNode = Node(parent, child.start, child.start + edgeLenth - 1, parent.depth + edgeLength)
parent.children[s[child.start]] = newNode
child.start += edgeLength
child.length -= edgeLength
newNode.children[s[child.start]] = child
child.parent = newNode
'''return''' newNode
Node slowScan(Node node, '''int''' start)
curNode = node
curPos = start + node.depth
'''while''' ''true''
'''if''' curNode.children[s[curPos]] == '''null'''
'''break'''
child = curNode.children[s[curPos]]
edgePos = 0
'''while''' child.start + edgePos <= child.end '''and''' s[child.start + edgePos] == s[curPos]
curPos++
edgePos++
'''if''' child.start + edgePos > child.end
curNode = child
'''else'''
curNode = split(curNode, child, edgePos)
'''break'''
'''return''' curNode
</code>
== Асимптотическая оценка ==
