WM>Так расскажи подробнее чего хочешь добиться, а не как это сейчас решаешь.
WM>Если тебе разные нужно регулярные выражения в коллекции строк искать, то это делается по другому. Нужно строить и поддерживать индексы. А тут уже возможны варианты: от быстрых но сложных суффиксных деревьев, до простых, но часто эффективных, n-грамных индексов (вот например). Ну и от вида поискового запроса выбор эффективного алгоритма зависит — вдруг у тебя там алфавит огромный или наоборот, или ограничение на максимальную длину замены «*» есть.

Спасибо за ссылки и подсказки буду изучать.
Да, нужен поиск как в словаре некотрого подмножества, только не с первой буквы а по какой то заданной маске (wildcard). Словарь лежит упорядоченный в лексографическом порядке.
O(n) — очень медленно.