Algorithm for multiple extended string matching I need to implement an algorithm for multiple extended string matching in text. Algorithms to match regular expression would be perhaps too slow.

Extended means the presence of wildcards (any number of characters instead of a star), for example:

abc*def //matches abcdef, abcpppppdef etc.


Multiple means that the search is going on simultaneously for multiple string patterns (not a separate search for each pattern), for example:

abc*def
abc
whatever
some*string


QUESTION:

What is the fast algorithm that can do multiple extended string matching?

Preferably, optimized for SIMD instructions and multicore implementation. Open source implementation (C/C++/Python) would be great as well. I'm interested in 10 Gbps+ performance on a single core of a modern CPU.

Thank you
Do you change the patterns often? If not, then you can use Aho-Corasick method, whose idea is, first, to build a finite automaton based on your patterns and, then, to make a single pass over the text with this automaton to find matches (if the automaton visits a "matching" state, then there is a match). The complexity of the automata building should be linear in the length of the patterns (# of patters * max pattern length), and the matching phase should be linear in the size of the text you search in.