Изменения
→Шаг 2. Преобразование бора.
\delta(\pi(u), c), &\text{else.}
\end{cases}</tex> {{---}} функция перехода.
Мы можем понимать рёбра бора как переходы в автомате по соответствующей букве. Однако одними только рёбрами бора нельзя ограничиваться. Если мы пытаемся выполнить переход по какой-либо букве, а соответствующего ребра в боре нет, то мы тем не менее должны перейти в какое-то состояние. Для этого нам и нужны суффиксные ссылки.
<br> Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{---}} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>.
Функции перехода и суффиксные ссылки можно найти либо алгоритмом [[Обход в глубину, цвета вершин | обхода в глубину]] с ленивыми вычислениями, либо с помощью алгоритма [[Обход в ширину | обхода в ширину]].
