Автономное индексирование по упорядоченному набору строк для поиска по шаблону

Question

Я хочу реализовать функцию поиска по шаблону для большого, но конечного набора строк, вот что я хочу: за 1 символ, * за 0 или более символов. Что я уже знал:

1. используйте trie, или варианты trie могут решить проблему довольно хорошо, БЕЗ * соответствия
2. хотя использование обратной задачи tree действительно решает проблему, объединяя результаты сопоставления обеих попыток, все же я хочу, чтобы строки были упорядочены по алфавиту, а память, используемая для вычисления пересечений, могла быть серьезной.

похожие проблемы были найдены на http://www.codechef.com/JAN10/problems/L2, но я не могу найти, чтобы кто-то объяснял их коды.

Спасибо

Answer 1

Это может быть достигнуто с помощью библиотеки регулярных выражений. Взгляните на то, что я реализовал. Библиотека регулярных выражений в C++