3622
правки
Изменения
→Псевдокод
root = Node(superRoot, 0, -1, 0)
root.suf = superRoot
'''for''' c '''in''' <tex>\Sigma</tex>:
superRoot.children[c] = root
head = root
'''for''' i = 1 '''to''' n:
head = addSuffix(head, i)
'''return''' root
Node fastScan(Node head):
'''if''' head {{---}} корень:
'''return''' head
'''if''' не существует суффиксной ссылки head:
skipped = head.length <font color=green> // Сколько символов нам осталось пропустить без проверки </font>
curPos = head.start <font color=green> // Текущая позиция на ребре, нужна для создания ребра по соответствующему символу </font>
'''if''' head совпадает с корнем:
skipped--
curPos++
curNode = head.parent.suf <font color=green> // Текущая вершина </font>
'''while''' непройденная длина больше длины ребра:
curNode = curNode.children[s[curPos]]
skipped -= curNode.length
curPos += curNode.length
'''if''' остались непройденные символы:
разделим ребро и запишем новую вершину в curNode
head.suf = curNode
curNode = node <font color=green> // Текущая вершина </font>
curPos = start + node.depth <font color=green> // Текущий символ суффикса </font>
'''while''' существует ребро по символу curPos:
child = curNode.children[s[curPos]] <font color=green> // Ребенок по символу суффикса </font>
edgePos = 0 <font color=green> // Текущая позиция на ребре </font>
'''while''' символы на ребре совпадают с суффиксом:
curPos++
edgePos++
'''if''' ребро пройдено до конца:
curNode = child
'''else''':
разделим ребро в месте несовпадения, запишем в curNode и выйдем из цикла
'''return''' curNode
