Изменения

Алгоритм МакКрейта

9 байт добавлено, 21:45, 6 мая 2014

→‎Псевдокод

Node fastScan(Node head):

~~если~~ '''if''' head {{---}} корень:

'''return''' head

~~если~~ '''if''' не существует суффиксной ссылки head:

skipped = head.length

curPos = head.start

~~если~~ '''if''' head совпадает с корнем:

skipped--

curPos++

curNode = head.parent.suf

~~пока~~ '''while''' непройденная длина больше длины ребра:

curNode = curNode.children[s[curPos]]

skipped -= curNode.length

curPos += curNode.length

~~если~~ '''if''' остались непройденные символы:

разделим ребро и запишем новую вершину в curNode

head.suf = curNode

curNode = node

curPos = start + node.depth

~~пока~~ '''while''' существует ребро по символу curPos:

child = curNode.children[s[curPos]]

edgePos = 0

~~пока~~ '''while''' символы на ребре совпадают с суффиксом:

curPos++

edgePos++

~~если~~ '''if''' ребро пройдено до конца:

curNode = child

~~иначе~~'''else''':

разделим ребро в месте несовпадения, запишем в curNode и выйдем из цикла

'''return''' curNode

120

правок