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