Изменения

Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.<BR>Например, шаблон <tex>ab\varphi\varphi c\varphi</tex> , который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки<tex>xabvccababcax</tex>. Надо для каждого заданного шаблона с масками находить все его вхождения в текст.<BR>Надо обнаружитьбезмасочные куски Для того, чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>:, надо обнаружить вхождения в текст всех его безмасочных кусков.<BR>

<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>. <BR>

1. <tex>\forall i = 1 \ldots m: C[i] = 0 </tex>, где <tex>m</tex> {{---}} длина текста. <BR>2. Используя алгоритм Ахо-Корасик, находим безмасочные подстроки шаблона <tex>Q</tex>: когда находим <tex>Q_i</tex>

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