The problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. We prove an upper and lower bound on the number of such different possible rotated patterns. Subsequently, given an m × m array (pattern) and an n × n array (text) over some finite alphabet Σ, we present a new method yielding an O(n2m3) time algorithm for this problem.
['Amihood Amir', 'Ayelet Butman', 'Maxime Crochemore', 'Gad M. Landau', 'Malka Schaps']
Two-dimensional pattern matching with rotations