Dekel Tsur

The most efficient currently known algorithms for two dimensional matching with rotation have a worst case time complexity of O(n²m ³), where the size of the text is n² and the size of the pattern is m2. In this paper we present two algorithms for the two dimensional rotated matching problem whose running time is O(n²m²). The preprocessing time of the first algorithms is O(m⁵) and the preprocessing time of the second algorithm is O(m⁴).