Two-dimensional pattern matching with k mismatches

摘要

We give an algorithm which finds all occurrences of an m1 × m2 pattern array embedded as subarrays in an n1 × n2 array of text, where at most k mismatches are allowed per occurrence. The algorithm runs in time O((k + a)(b log b + n1n2)), where a = min(m1, m2) and b = max(m1, m2). This improves upon the previously best known algorithm, and is asymptotically optimal for k ≈ a.