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