Изменения

Каждое появление безмасочной подстроки <tex>Q</tex> увеличивает значение одной ячейки <tex>C</tex> на <tex>1</tex>, и значение каждой ячейки может увеличиваться до <tex>k</tex> раз, что будет означать появление шаблона в тексте на позиции этой ячейки.<BR>

Поиск подстрок заданного шаблона с помощью алгоритма Ахо-Корасик выполняется за время <tex>O(m+n+a)</tex>, где <tex>n</tex> {{---}} суммарная длина подстрок, то есть длина шаблона, <tex>m</tex> {{---}} длина текста, <tex>a</tex> {{---}} количество появлений подстрок шаблона. Далее просто надо пробежаться по массиву <tex>C</tex> и просмотреть значения ячеек за время <tex>O (m)</tex>.

== Источники ==