On pattern matching with k mismatches and few don't cares

In this paper we give an algorithm whose runtime increases with the number of don't cares. We define an island to be a maximal length substring of P that does not contain don't cares. Let q be the number of islands in P. We present an algorithm that runs in O(nklog⁡m+nmin⁡{qklog2⁡m3,qlog⁡m}) time. If the number of islands q is O(k) this runtime becomes O(nklog⁡m), which essentially matches the best known runtime for pattern matching with k mismatches without don't cares. If the number of islands q is O(k2), this algorithm is asymptotically faster than the previous best algorithm for pattern matching with k mismatches with don't cares in the pattern.