Изменения
Нет описания правки
}
Кроме этих функций требуется инициализация, но она имеет отношение только к кодированию, поэтому здесь приведена не будет.
== Поиск шаблонов с масками ==
Пусть <tex>\phi</tex> {{---}} маска, обозначающая любой одиночный символ.<BR>
Например, шаблон <tex>ab\phi\phi c\phi</tex> встречается на позициях 2 и 8 строки
<tex>xabvccababcax</tex>.<BR>
Если количество <tex>\phi</tex> ограничено сверху константой, то шаблоны с
масками могут быть выявлены за линейное время. Для этого надо обнаружить
безмасочные куски шаблона <tex>Q</tex>:<BR>
Пусть {<tex>Q_1</tex>, ..., <tex>Q_k</tex>} {{---}} набор подстрок
<tex>Q</tex>, разделенных масками, и пусть <tex>l_1</tex>, ...,
<tex>l_k</tex> {{---}} их стартовые позиции в <tex>Q</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>
в тексте T на позиции <tex>j</tex>, увеличиваем на единицу <tex>C[j - l_i + 1]</tex>.<BR>
3. Каждое <tex>i</tex>, для которого <tex>C[i] = k</tex>, является
стартовой позицией появления шаблона <tex>Q</tex>.
== Источники ==
