Изменения
Первая версия статьи (статья ещё не дописана)
{{В разработке}}
== Задача алгоритма ==
Найти для каждого образца из заданного множества образцов все его вхождения в текст за время <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 />
4) <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]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.
== Задача алгоритма ==
Найти для каждого образца из заданного множества образцов все его вхождения в текст за время <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 />
4) <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]</tex> - максимальный суффикс <tex>[u]</tex>, <tex>[v]\neq[u]</tex>. Обозначение: <tex>[u]</tex> - слово, приводящее в вершину <tex>u</tex> в боре.
