275
правок
Изменения
→Реализация
'''Node''' suffixLink
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
'''Node''' buildSuffixTree(s):
'''int''' n = s.length()
'''byte''' a[n]
'''for''' i = 0..n
a[i] = (byte) ALPHABET.indexOf(s.charAt([i]))in ALPHABET '''Node''' root = new '''Node'''(0, 0, 0, null);
'''Node''' node = root
'''for''' i, tail = 0..n
last = null
'''else'''
'''byte ''' t = a[ch.begin + tail]
'''if''' t == a[i]
'''if''' last <tex>\ne</tex> null
'''break'''
'''else'''
'''Node ''' splitNode = new Node(ch.begin, ch.begin + tail, node.depth + node.end - node.begin, node)
splitNode.children[a[i]] = new Node(i, n, ch.depth + tail, splitNode)
splitNode.children[t] = ch
