Exact and Approximate Two Dimensional Pattern Matching allowing Rotations

Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen

We give fast filtering algorithms for searching a 2-dimensional pattern in a 2-dimensional text allowing any rotation of the pattern. We consider the cases of exact and approximate matching under several matching models, improving the previous results. For a text of size n x n character and a pattern of size m x m characters, the exact matching takes average time O(n^2/m). If we allow k-mismatches of characters, then our best algorithm achieves O(n^2 sqrt(k)/m) average time, for reasonable error levels. For large k, we obtain a O(n^2 k^(3/2) sqrt(log m)/m) average time algorithm. We generalize the algorithms for the matching model where the sum of absolute differences between characters is at most k.