Technical Report No. 51, March 1994 - Abstract

Robert Friedrich, Thomas Ottmann, Sven Schuierer:
Two Dimensional String Matching for Non-Rectangular Patterns

The two dimensional string matching problem is to find the occurrences of a two dimensional pattern in a two dimensional text. Usually, the pattern is assumed to be a rectangle or even a square. In this paper we show how to adapt existing two dimensional string matching algorithms to triangular and other non-rectangular patterns without loss of efficiency. Moreover, we charaterize the patterns that fulfill a necessary consistency condition used in most two dimensional string matching algorithms and show how to recognize efficiently those patterns that fulfill the consistency condition.