Two-dimensional pattern matching

In computer science, two-dimensional pattern matching is the problem of locating occurrences of a two-dimensional matrix of characters ("the pattern") in a bigger two-dimensional matrix ("the picture", or, in analogy with string searching, "the text").

The naïve solution

Assume given a pattern $P[m\times m]$ and a picture $T[n\times n]$, where $m\leq n$. The simplest approach is to compare P against every sub-array of size </math>m\times m</math> in T. This algorithm has a worst-case time of $\Theta ((n-m+1)^{2}m^{2})$. It is usually assume that math>m\le n/2</math>, whence this can be written as math>\Theta(n^2m^2)</math>.