Изменения

Перейти к: навигация, поиск

Алгоритм Ахо-Корасик

197 байт добавлено, 05:55, 18 июня 2014
Алгоритм поиска
# Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <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>QT[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>kQ_1</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>.
Анонимный участник

Навигация