Изменения

Перейти к: навигация, поиск

Алгоритм Ахо-Корасик

6 байт убрано, 03:37, 18 июня 2014
→‎Шаг 2
Узлы бора, в которых заканчиваются образцы, становятся терминалами.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br />
1) *<tex>parent(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br />2) *<tex>\pi(u) = \delta(\pi(parent(u)), c)</tex> {{---}} суффиксная ссылка; здесь <tex>u</tex> {{---}} сын <tex>parent(u)</tex> по символу <tex>c</tex>;<br />3) *<tex>\delta(u, c) =
\begin{cases}
v\text{, if $v$ is son by symbol $c$ in trie;}\\
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/39683»

Навигация