Изменения

|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf, \ head_i</tex> с неопределенными суффиксными ссылками. Покажем, что это невозможно. Рассмотрим, что значит, что <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>parent</tex> {{- --}} предок;* <tex>start, \ end</tex> {{--- }} позиции строки, соответствующие ребру до предка; <tex>s[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>.Пусть глобально известна строка <tex>s</tex> со специальным символом на конце, ее длина <tex>n</tex> и используемый алфавит <tex>\Sigma</tex>.

'''string''' s '''int''' n = s.length  Node buildSuffixTree():

'''for''' c '''in''' <tex>\Sigma</tex>:

'''for''' i = 1 '''to''' n:

Node addSuffix(Node head, '''int''' start):

Node fastScan(Node head): '''if''' head.depth == 0: '''return''' head '''if''' head.suf == '''null''':

'''while''' curNode.children[s[curPos]].length <tex>\leqslant</tex>= skipped:

'''if''' skipped > 0:

head.suf = newNode

Node split(Node parent, Node child, '''int''' edgeLength): newNode inserted = Node(parent, child.start, child.start + edgeLenth - 1, parent.depth + edgeLength) parent.children[s[child.start]] = newNodeinserted

newNodeinserted.children[s[child.start]] = child child.parent = newNodeinserted '''return''' newNodeinserted

Node slowScan(Node node, '''int''' start):

'''while''' ''true'' '''if''' curNode.children[s[curPos]] !== '''null''' '''break''' :

'''while''' child.start + edgePos <= tex>\leqslant</tex> child.end '''and''' s[child.start + edgePos] == s[curPos] :

'''if''' child.start + edgePos > child.end:

'''else''':