A new approach to two-dimensional pattern matching allowing errors

Given a text of size n×n and a pattern of size m×m, the exact matching is to find all occurrences of the pattern in the text, while the approximate matching is to find all the locations of m×m blocks in the text that differ by at most k mismatches. We present a new algorithm for exact matching, which runs in O(n² log|Σ|), Σ={a₁,a₂,…a_|Σ|} is the alphabet of the pattern, and for approximate matching, in O(n² log|Σ|+hm²), which consists of two stages. The first stage is to preselect h subblocks of size s×s, 0⩽s⩽m that exactly match the pattern. The second stage of verification compares the blocks containing these h subblocks to determine if the number of mismatches is less than k