Изменения

Перейти к: навигация, поиск

Алгоритм Ахо-Корасик

83 байта добавлено, 13:32, 5 июня 2016
Шаг 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 />Сжатые Аналогично обычным суффиксным ссылкам сжатые суффиксные ссылки могут отыскиваться быть найдены при помощи ленивой рекурсии.
== Использование автомата ==

Навигация