3622
правки
Изменения
м
'''int''' length
'''int[]''' suf
'''int[]''' lcp
псевдо-правки
===Наивный алгоритм===
Рассмотрим наивный алгоритм построения суффиксного дерева строки <tex>s</tex>:
go[0] = new Vertex() //корень count = 0 //номер последней вершины, созданной в дереве (глобальная переменная) '''for''' i = 0 '''to''' n : //для каждого символа строки insert(i, n) //добавляем суффикс, начинающийся с него
insert(l, r):
cur = 0
'''while''' (l < r): '''if''' go[cur][s[l]].v == -1 '''then''' : //если мы не можем пойти из вершины по символу <tex> l </tex> createVertex(cur, l, r) //создаем новую вершину '''else:'''
start = go[cur][s[l]].l
finish = go[cur][s[l]].r
hasCut = false
'''for''' j = start '''to''' finish : //для каждого символа на ребре из текущей вершины '''if''' s[l+j-start] <tex> \neq </tex> s[j] '''then''' : //если нашли не совпадающий символ //создаем вершину на ребре
old = go[cur][s[l]]
createVertex(cur, l, j - 1)
hasCut = true
'''break'''
'''if''' !hasCut '''then''': cur = go[cur][s[l]].v //переходим по ребру l = l + finish - start //двигаемся по суффиксу на длину подстроки, записанной на ребре '''else:'''
'''break'''
createVertex(cur, l, r)
go[++count] = new Vertex()
go[cur][s[l]].v = count
go[cur][s[l]].l = l
<code>
Node addNextSuffix(Node previous, '''int''' length, '''int''' lcp): '''if''' previous.depth == 0 '''or''' previous.depth == lcp : <font color=green> // Добавляем к сыновьям текущей вершины </font>
added = Node(previous, length)
previous.children.'''push'''(added)
'''return''' added
'''else:''' '''if''' previous.parent.depth < lcp : <font color=green> // Нужно разрезать ребро </font>
inserted = Node(prevous.parent, lcp)
previous.parent.children.'''pop'''()
'''return''' addNextSuffix(previous.parent, length, lcp)
Node buildSuffixTree('''int[]''' suf, '''int[]''' lcp, '''int''' length):
root = Node('''null''', 0)
previous = root
'''for''' i = 1 '''to''' length :
previous = addNextSuffix(previous, length - suf[i], lcp[i])
'''return''' root
<code>
'''function''' calculatePositions(Node parent, Node child, '''int''' stringLength):
start = stringLength - child.maxDepth + parent.depth
end = start + child.depth - parent.depth - 1
<code>
'''int''' curPos = 0
Node minNode = root
<font color=green>//Для заполнения нужно вызвать dfs(root) </font> '''function''' dfs(Node n): '''if''' children.size == 0:
suf[curPos] = length - n.depth
lcp[curPos] = minNode.depth
curPos++
minNode = n
'''else:''' '''foreach''' Node c child '''fromin''' n.children: '''if''' n.depth < minNode.depth:
minNode = n
dfs(cchild)
</code>
