The most efficient currently known algorithms for two dimensional matching with rotation have a worst case time complexity of O(n 2 m 3 ), where the size of the text is n 2  and the size of the pattern is m 2 . In this paper we present two algorithms for the two dimensional rotated matching problem whose running time is O(n 2 m 2 ). The preprocessing time of the first algorithms is O(m 5 ) and the preprocessing time of the second algorithm is O(m 4 ).
['Amihood Amir', 'Oren Kapah', 'Dekel Tsur']
Faster two dimensional pattern matching with rotations