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(n
2
m
3) time algorithm for this problem.
Keywords Design and analysis of algorithms - two-dimensional pattern matching - rotation
Part of this research was conducted while the first and fourth authors were visiting the University of Marne-La-Vallée supported
by Arc-en-Ciel/Keshet, French-Israeli Scientific and Technical Cooperation Program.
Partially supported by NSF grant CCR-01- 04494, ISF grant 282/01, and an Israel-France exchange scientist grant funded by
the Israel Ministry of Science.
partially supported by CNRS, NATO Science Programme grant PST.CLG.977017, and by Arc-en-Ciel/Keshet, French-Israeli Scientific
and Technical Cooperation Program.
partially supported by NSF grants CCR-9610238 and CCR-0104307, by NATO Science Programme grant PST.CLG.977017, by the Israel
Science Foundation grants 173/98 and 282/01, by the FIRST Foundation of the Israel Academy of Science and Humanities, by IBM
Faculty Partnership Award, and by Arc-en-Ciel/Keshet, French-Israeli Scientific and Technical Cooperation Program.