Optimal trade-offs for pattern matching with $k$ mismatches

Abstract

Given a pattern of length $m$ and a text of length $n$, the goal in $k$-mismatch pattern matching is to compute, for every $m$-substring of the text, the exact Hamming distance to the pattern or report that it exceeds $k$. This can be solved in either $\tilde{O}(n\sqrt{k})$ time as shown by Amir et al. [J. Algorithms 2004] or $\tilde{O}((m+k^2)\cdot n/m)$ time due to a result of Clifford et al. [SODA 2016]. We provide a smooth time trade-off between these two bounds by designing an algorithm working in time $\tilde{O}((m+k\sqrt{m})\cdot n/m)$. We complement this with a matching conditional lower bound, showing that a significantly faster combinatorial algorithm is not possible, unless the combinatorial matrix multiplication conjecture fails.