Fast Two Dimensional Pattern Matching

A new algorithm for searching a two dimensional $m \times m$ pattern in a two dimensional $n \times n$ text is presented. It performs on the average less comparisons than the size of the text: $n^2 \over m$ using $m^2$ extra space. Basically, it uses multiple string matching on only $n/m$ rows of the text. It runs in at most $3n^2$ time, and is closed to optimal $n^2$ for many patterns. It readily extends to an alphabet independent algorithm with a $5n^2$ worst case. Experimental results are also included, for a rough but practical version.