Изменения
→Шаг 2. Преобразование бора.
=== Шаг 2. Преобразование бора. ===
'''Обозначения''': <tex>[u]</tex> {{---}} слово, приводящее в вершину <tex>u</tex> в боре.<br />
Узлы бора можно понимать как состояния автомата, а корень {{---}} как начальное состояние.<br />
Узлы бора, в которых заканчиваются строк, становятся терминалами.<br />
Для переходов по автомату заведём в узлах несколько функций:<br />
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину ]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
==== Пример автомата Ахо-Корасик ====
[[Файл:axo.jpg]]<br />
