Изменения
Нет описания правки
}
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
== Поиск шаблонов с масками ==
=== Постановка задачи ===Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.Например, шаблон <tex>ab\varphi\varphi c\varphi</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>ab\varphi\varphi c\varphi</tex> содержит две подстроки без масок <tex>ab</tex> и <tex>c</tex> и их стартовые позиции соответственно <tex>1</tex> и <tex>5</tex>. <tex>C[i]</tex> {{---}} количество встретившихся в тексте безмасочных подстрок шаблона, который начинается в тексте на позиции <tex>i</tex>. Тогда появление подстроки <tex>Q_i</tex> в тексте на позиции <tex>j</tex> будет означать возможное появление шаблона на позиции <tex>j - l_i + 1</tex>. <BR>=== Алгоритм поиска:<BR>===1. # Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex>в тексте <tex>T</tex> на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR>2. # Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, являетсястартовой позицией появления шаблона <tex>Q</tex> в тексте.<BR>Каждое появление безмасочной подстроки <tex>Q </tex> увеличивает значение одной ячейки <tex>C</tex> на <tex>1</tex>, и значение каждой ячейки может увеличиваться до <tex>k</tex> раз, что будет означать появление шаблона в тексте на позиции этой ячейки. == Время работы алгоритма поиска шаблонов с масками ==
Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.
