Example

The figure shows an irregular pattern $P$. It fits in a $3\times 3$ box and has 2 occurrences in $T$, one of them is shown.

Problem 44: Searching Irregular 2D Patterns

Let $P$ be a given (potentially) irregular two-dimensional (2D) pattern. By irregular is meant that $P$ is not necessarily a rectangle, it can be of any shape. The aim is to find all occurrences of $P$ in a 2D $n\times n'$ text $T$ of total size $N=n n'$.

Show that two-dimensional pattern matching of irregular 2D-patterns can be done in $O( N\log N) $ time.

References

A. Amir and M. Farach. Efficient matching of nonrectangular shapes. Ann. Math. Artif. Intell., 4:211-224, 1991.

125 Problems in Text Algorithms

Example

Problem 44: Searching Irregular 2D Patterns

References