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.