3622
правки
Изменения
→Шаг 3. Построение сжатых суффиксных ссылок
===Шаг 3. Построение сжатых суффиксных ссылок ===
При построении автомата может возникнуть такая ситуация, что ветвление есть не на каждом символе. Тогда можно маленький бамбук заменить одним ребром. Для этого и используются сжатые суффиксные ссылки.
<tex>up(u) =
\begin{cases}
\varnothing,&\text{if $\pi(u)$ is root;}\\
up(\pi(u)), &\text{else.}
\end{cases}</tex> где <tex>up</tex> {{---}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />Сжатые Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут отыскиваться быть найдены при помощи ленивой рекурсии.
== Использование автомата ==
