Изменения

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

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

303 байта добавлено, 18:01, 29 марта 2011
Шаг 2: Добавляю пример автомата АК
Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.<br />
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
=== Пример автомата Ахо-Корасик ===
[[Файл:Aho-corasick2.jpg]]<br />
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
== Шаг 3 ==
141
правка

Навигация