Streaming Pattern Matching with d Wildcards

Shay Golan, Tsvi Kopelowitz, Ely Porat

In the pattern matching with $d$ wildcards problem one is given a text $T$ of length $n$ and a pattern $P$ of length $m$ that contains $d$ wildcard characters, each denoted by a sp…