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