Given a set of string patterns, find which ones match a particular string I have an array of known patterns with optional wildcards. For example this array that has 5 patterns:


ab*e
hkl
abcd*
ab
sdfs?f


now I need to find the elements within the array that match an arbitrary string.

This can be solved with regular expression by converting the patterns to regexp and looping over the array and returning those that match my string. The problem is that this approach is too slow when my patterns array has thousands of patterns.

I'm looking for some sort of hashing to the known patterns array (could be slow as it only happens once), so that the search of matched patterns to a gives string becomes significantly faster. I checked the Rabin Karp and Aho–Corasick algorithms but they don't work for patterns with wildcards.

In the example above if I'm looking for all matched patterns for abcde I would get


ab*d
abcd*


or the values 0,2 which are the indexes in the patterns array matching my string.
Rather than build 5 NFAs (one for each pattern), I suggest you build a single NFA or DFA that represents the parallel composition of all five patterns.  Then you can run the string through this automaton and check what state it ends at.  That state will tell you which of the 5 patterns it matches.

For best performance, build a NFA for each pattern, take the parallel composition using the product construction, and then convert to a DFA.  This should be quite fast.