141
правка
Изменения
Продолжение статьи
v\text{, if $v$ is son by symbol $c$ in trie;}\\
\delta(\pi(u), c)\text{, else.}
\end{cases}</tex> - функция перехода;.<br /><br />4Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.<br />Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину. == Шаг 3 ==Построение сжатых суффиксных ссылок.<br /><tex>up(u) =
\begin{cases}
\pi(u)\text{, if $\pi(u)$ is terminal;}\\
\emptyset\text{, if $\pi(u)$ is root;}\\
up(\pi(u))\text{, else.}
\end{cases}</tex> - сжатая суффиксная ссылка, т.е.<br /><br />Суффиксная ссылка <tex>\piближайшее допускающее состояние (uтерминал) перехода по суффиксным ссылкам. == vИспользование автомата ==По очереди просматриваем символы текста. Для очередного символа </tex>, если <tex>[v]c</tex> - максимальный суффикс переходим из текущего состояния <tex>[u]</tex>в состояние, которое вернёт функция <tex>[v]\neq[delta(u], c)</tex>. Обозначение: <tex>[u]</tex> - словоОказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, приводящее в вершину <tex>u</tex> в борето соответствующие ему образцы тоже отмечаем.
