275
правок
Изменения
→Реализация
'''int''' begin
'''int''' end
'''Node''' parent
'''Node[]''' children
'''Node''' suffixLink
'''function''' buildSuffixTree(s):
'''int''' n = s.length()
'''Node''' node = root
'''int''' tail = 0
'''for''' i = 0..n
'''while''' tail <tex>\geqslant</tex> 0
'''Node''' ch = node.children[as[i - tail]]
'''while''' ch <tex>\ne</tex> null && tail <tex>\geqslant</tex> ch.end - ch.begin
tail -= ch.end - ch.begin
node = ch
ch = ch.children[as[i - tail]]
'''if''' ch == null
node.children[as[i]] = new Node(i, n, node.depth + node.end - node.begin, node)
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
last = null
'''else'''
'''if''' last <tex>\ne</tex> null
last.suffixLink = node
'''break'''
'''else'''
'''Node''' splitNode = new Node(ch.begin, ch.begin + tail, node.depth + node.end - node.begin, node) splitNode.children[as[i]] = new Node(i, n, ch.depth + tail, splitNode)
splitNode.children[t] = ch
ch.begin += tail
ch.parent = splitNode
node.children[as[i - tail]] = splitNode
'''if''' last <tex>\ne</tex> null
last.suffixLink = splitNode
'''else'''
node = node.suffixLink
tail++
'''return''' root
