On the Average-case Complexity of Pattern Matching with Wildcards

In this paper we present a number of fast average-case algorithms for pattern matching with wildcards. We consider the problems where wildcards are restricted to either the pattern or the text, however, the results can be easily adapted to the case where wildcards are allowed in both. We analyse the algorithms \textit{average-case} complexity and their \textit{expected-case} complexity and show new lower bounds for the average-case complexity of the problems. To the best of our knowledge these are the first results on the average-case complexity of wildcard matching.