A filtering algorithm for k-mismatch with don't cares

We present a filtering based algorithm for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols in either p or t (but not both), and a bound k, our algorithm finds all the places that the pattern matches the text with at most k   mismatches. The algorithm is deterministic and runs in Θ(nm1/3k1/3log2/3m)Θ(nm1/3k1/3log2/3m) time.

Research highlights► Faster filtering for pattern matching with don't cares. ► Approximate matching with wildcards can be achieved using filtering techniques. ► Uniform sampling of mismatches solved using filtering and randomised algorithms.