Привет!

Подскажите, пожалуйста, хороший (т.е. эффективный в плане скорости) алгоритм для следующей задачи.

На вход функции подается текстовая строка. Нужно проверить, совпадает ли она по маске с
хотя бы одной строкой из списка правил. Каждое правило — это текстовая строка, которая может
содержать wildcard-символ *. Приведу пример:

Ввод: /path/hello.txt
Правила: *.pdf;*.txt;*someapp*;*path*/*ello*

(здесь будут совпадения по *.txt и по *path*/*ello*)

Предполагаем, что такие проверки выполняются много-много раз в секунду, а сам список правил
содержит тысячи и даже миллионы элементов. Хотелось бы не проходить по всему списку, а
использовать что-то вроде двоичного поиска.

Список правил формируется динамически, во время работы программы, поэтому строить из него
какую-то предкомпилированную модель нельзя. Также нельзя использовать средства с динамической
генерацией кода (JIT и т.п.) — такие ограничения среды.

Хочется найти не столько реализацию (C/C++), сколько описание самого алгоритма.

Спасибо!