Matching with don't-cares and a small number of mismatches

In matching with don't-cares and k mismatches we are given a pattern of length m and a text of length n, both of which may contain don't-cares (a symbol that matches all symbols), and the goal is to find all locations in the text that match the pattern with at most k mismatches, where k is a parameter. We present new algorithms that solve this problem using a combination of convolutions and a dynamic programming procedure. We give randomized and deterministic solutions that run in time O(nk²logm) and O(nk³logm), respectively, and are faster than the most efficient extant methods for small values of k. Our deterministic algorithm is the first to obtain an O(polylog(k)⋅nlogm) running time.