k-mismatch with don't cares

We give the first non-trivial algorithms 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 and a bound $k$, our algorithms find all the places that the pattern matches the text with at most $k$ mismatches. We first give an $O(n(k+\log{m}\log\log{m})\log{m})$ time randomised solution which finds the correct answer with high probability. We then present a new deterministic $O(nk^2\log^3{m})$ time solution that uses tools developed for group testing and an approach based on $k$-selectors that runs in $O(nk polylog(m))$ time. Further, the location of the mismatches at each alignment is also given at no extra cost.