Простое решение можно реализовать через префиксное дерево. Запихиваем все шаблоны, а потом сравниваем по строчке из множества.
Если требуется сделать разово и на большом объеме данных, я бы поступил так. Определим на строках обычный лексикографический порядок (если есть строка и её префикс, то префикс меньше). Каждому шаблону со звездочкой {s}* сопоставим две строки {s} и {s}$, где $ больше 0 и 1. Шаблону без звезды, просто ставим {s} и {s}&, где & < 0 и 1. А теперь, начиная с первого символа, запускаем цифровую сортировку на строках, полученных из шаблона, + проверяемых строках.
В полученной последовательности шаблоны образуют скобочную последовательность. Все, что находится внутри скобок матчится с соответствующим шаблоном.
Из положительного, это сделать проще, когда строки не влезают в память. Число разрядов на сравнение можно ограничить длиной самого длинного шаблона.
