188
правок
Изменения
Нет описания правки
* Переходы хранятся в массиве отображений (ключ {{---}} символ, значение {{---}} номер состояния) <tex>edges</tex>,
* Суффиксные ссылки хранятся в массиве <tex>link</tex>,
* Длины строк хранятся в массиве <tex>len</tex>,* Функция <tex>newState</tex> создаёт новое состояние и возвращает его номер,* Функция <tex>clone</tex> копирует состояние и возвращает номер нового состояния.
'''func''' addChar(c)''':'''
p = last
'''while''' p >= 0 '''and''' edges[p].find(c) == edges[p].end()''':'''
edges[p][c] = rcur
p = link[p]
q = edges[p][c]
'''if''' len[p] + 1 == len[q]''':'''
link[rcur] = q
'''else:'''
new = clone(q) <font color="green">// скопируем состояние <tex>q</tex></font>
len[new] = len[p] + 1
link[q] = link[rcur] = new
'''while''' p >= 0 '''and''' edges[p][c] == q''':'''
edges[p][c] = new
p = link[p]
last = rcur
==Источники информации==
