Изменения

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

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

2 байта добавлено, 22:08, 13 мая 2016
Поиск шаблонов с масками
== Поиск шаблонов с масками ==
 
{{Задача
|definition = Пусть <tex>\varphi</tex> {{---}} маска, обозначающая любой одиночный символ.Например, шаблон <tex>ab\varphi\varphi c\varphi</tex>, который содержит в себе три маски, встречается на позициях <tex>2</tex> и <tex>8</tex> строки <tex>xabvccababcax</tex>. Необходимо найти для каждого заданного шаблона с масками все его вхождения в текст.<BR>
=== Алгоритм поиска ===
 
Для того чтобы найти все вхождения в текст заданного шаблона с масками <tex>Q</tex>, необходимо обнаружить вхождения в текст всех его безмасочных кусков.<BR>
Пусть <tex>\{Q_1, \dots, Q_k \}</tex> {{---}} набор подстрок
313
правок

Навигация