Изменения
Нет описания правки
== Поиск шаблонов с масками ==
Пусть <tex>\phivarphi</tex> {{---}} маска, обозначающая любой одиночный символ.<BR>Например, шаблон <tex>ab\phivarphi\phi varphi c\phivarphi</tex> встречается на позициях <tex>2 </tex> и <tex>8 </tex> строки
<tex>xabvccababcax</tex>.<BR>
безмасочные куски шаблона <tex>Q</tex>:<BR>
Пусть <tex>\{</tex><tex>Q_1</tex>, ..., <tex>Q_k</tex><tex>\} </tex> {{---}} набор подстрок
<tex>Q</tex>, разделенных масками, и пусть <tex>l_1</tex>, ...,
<tex>l_k</tex> {{---}} их стартовые позиции в <tex>Q</tex>, <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>.<BR>Алгоритм поиска:<BR>
1. <tex>\forall i = 1 \ldots m: C[i] = 0 </tex>, где <tex>m</tex> {{---}} длина текста. <BR>
2. Используя АКалгоритм Ахо-Корасик, находим подстроки <tex>Q</tex>: когда находим <tex>Q_i</tex>в тексте <tex>T </tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR>
3. Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является
стартовой позицией появления шаблона <tex>Q</tex> в тексте. == Время работы алгоритма поиска шаблонов с масками ==Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.
== Источники ==
