Wildcard string matching
algorithm
Solution
There is a paper covering the fastest options here http://swtch.com/~rsc/regexp/regexp1.html in particular it allows you avoid naive algorithms that become pathologically slow when long patterns are used.
It covers generic regular expressions but you can limit your implementation to the subset you require.
Problem
What is the most efficient wildcard string matching algorithm? I am asking only about an idea, it is not necessary to provide actual code. I'm thinking that such algorithm can be built with sorted suffix arrays, which can yield performance of O(log(n)). Am I correct? Edited: I mean patterns like `"A*B"`, `"*sip*"` or `"A?B"` where star means any number of symbols and question mark means single symbol.