Practical KMP/BM Style Pattern-Matching on Indeterminate Strings

Hossein Dehghani, Neerja Mhaskar, W. F. Smyth

In this paper we describe two simple, fast, space-efficient algorithms for finding all matches of an indeterminate pattern $p=p[\mathrm{1..}m]$ in an indeterminate string $x=x[\mathrm{1..}n]$, w…