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