On the Average-case Complexity of Pattern Matching with Wildcards

Carl Barton

Pattern matching with wildcards is the problem of finding all factors of a text $t$ of length $n$ that match a pattern $x$ of length $m$, where wildcards (characters that match eve…