275
правок
Изменения
м
→Реализация
'''Node''' root = new '''Node'''(0, 0, 0, null);
'''Node''' node = root
'''for''' (int i = 0, tail = 0; i < ..n; i++, tail++)
'''Node''' last = null
'''while''' tail <tex>\geqslant</tex> 0
'''Node''' ch = node.children[a[i - tail]]
'''while''' (ch != <tex>\ne</tex> null && tail <tex>\geqslant</tex> ch.end - ch.begin)
tail -= ch.end - ch.begin
node = ch
'''if''' ch == null
node.children[a[i]] = new Node(i, n, node.depth + node.end - node.begin, node)
'''if''' (last != <tex>\ne</tex> null) last.suffixLink = node
last = null
'''else'''
byte t = a[ch.begin + tail]
'''if''' t == a[i]
'''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[a[i]] = new Node(i, n, ch.depth + tail, splitNode)
ch.parent = splitNode
node.children[a[i - tail]] = splitNode
'''if''' last != <tex>\ne</tex> null
last.suffixLink = splitNode
last = splitNode
'''if''' node == root
--tail
'''else'''
node = node.suffixLink
'''return''' root
