Изменения
Нет описания правки
{{Задача
|definition = Найти для каждого образца из заданного множества образцов, размером Дан набор строк в алфавите размера<tex>k</tex> суммарной длины <tex>m</tex>, . Найти для каждой строки все его ее вхождения в текст за время <tex>O(m)</tex> и <tex>O(mk)</tex> памяти.
}}
==Алгоритм==
=== Шаг 1. Построение бора ===
Строим [[Бор|бор]] из строк.<br />
Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина строк.
== Шаг 1 ==Строим [[Бор|бор]] из образцов.<br />Построение выполняется за время <tex>O(m)</tex>, где <tex>m</tex> {{---}} суммарная длина образцов. === Пример построенного бора ====Бор для набора образцов строк <tex> \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} </tex>:<br />
[[Файл:Бор.jpg]]
=== Шаг 2 . ===
Превращаем бор в автомат.<br />
Узлы бора становятся состояниями автомата; корень {{---}} начальное состояние.<br />
Узлы бора, в которых заканчиваются образцыстрок, становятся терминалами.<br /><br />
Для переходов по автомату заведём в узлах несколько функций:<br />
*<tex>parent(u)</tex> {{---}} возвращает родителя вершины <tex>u</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 />
Функции перехода и суффиксные ссылки можно найти либо алгоритмом обхода в глубину с ленивыми вычислениями, либо с помощью алгоритма обхода в ширину.
==== Пример автомата Ахо-Корасик ====
[[Файл:axo.jpg]]<br />
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
=== Шаг 3 ==. Построение сжатых суффиксных ссылок.<br />===
<tex>up(u) =
\begin{cases}
== Использование автомата ==
По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцыстроки, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы строки тоже отмечаем.<br />''Примечание.'' Если требуется найти только первое вхождение образца строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
== Пример реализации ==
'''char''' charToParent <font color=green>// символ, ведущий к родителю</font>
'''bool''' leaf <font color=green>// флаг, является ли вершина терминалом</font>
'''vector <int>''' leafPatternNumber <font color=green>// номера образцовстрок, за которые отвечает терминал</font>
'''Функция, для вычисления суффиксной ссылки:'''
'''return''' v->up
'''Функция, для добавление образца строки в бор:'''
'''fun''' addString('''string const&''' s, '''int''' patternNumber):
'''Node*''' cur = root
cur->leaf = ''true''
cur->leafPatternNumber.push_back(patternNumber)
'''Функция, для процессинга текста (поиск, встречается образец строка или нет):''' '''fun''' processText('''string const&''' t, '''vector<bool>&''' found): <font color=green>// found - это вектор, длина которого равна количеству образцовстрок</font> found.assign(w, ''false'') <font color=green>// w - количество образцовстрок</font>
'''Node*''' cur = root
'''for''' i = 0 '''to''' t.length - 1
