Изменения
Нет описания правки
== Задача алгоритма ==
Найти для каждого образца из заданного множества образцов все его вхождения в текст за время <tex>O(m+n+a)</tex>, где <tex>m</tex> {{- --}} суммарная длина образцов, <tex>n</tex> {{--- }} длина текста, <tex>a</tex> {{--- }} размер ответа (количество пар). В худшем случае <tex>a=nk</tex>, но он случается редко.
== Шаг 1 ==
Строим бор из образцов. См. [[Бор]].<br />
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{- --}} суммарная длина образцов.
=== Пример построенного бора ===
== Шаг 2 ==
Превращаем бор в автомат.<br />
Узлы бора становятся состояниями автомата; корень {{- --}} начальное состояние.<br />
Узлы бора, в которых заканчиваются образцы, становятся терминалами.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br />
1) <tex>parent(u)</tex> {{- --}} возвращает родителя вершины <tex>u</tex>;<br />2) <tex>\pi(u) = \delta(\pi(parent(u)), c)</tex> {{--- }} суффиксная ссылка; здесь <tex>u</tex> {{--- }} сын <tex>parent(u)</tex> по символу <tex>c</tex>;<br />
3) <tex>\delta(u, c) =
\begin{cases}
v\text{, if $v$ is son by symbol $c$ in trie;}\\
\delta(\pi(u), c)\text{, else.}
\end{cases}</tex> {{- --}} функция перехода.<br /><br />Суффиксная ссылка <tex>\pi(u) = v</tex>, если <tex>[v]</tex> {{--- }} максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> {{--- }} слово, приводящее в вершину <tex>u</tex> в боре.<br />
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
=== Пример автомата Ахо-Корасик ===
\emptyset\text{, if $\pi(u)$ is root;}\\
up(\pi(u))\text{, else.}
\end{cases}</tex> {{- --}} сжатая суффиксная ссылка, т.е. ближайшее допускающее состояние (терминал) перехода по суффиксным ссылкам.<br /><br />
Сжатые суффиксные ссылки могут отыскиваться при помощи ленивой рекурсии.
