Two Dimensional String Matching for Non-Rectangular Patterns
Robert J. Friedrich, Thomas Ottmann, Sven Schuierer · 1994
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 this consistency condition. This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/8-1. 248 1 Introduction String matching is a very well studied area in computer science [Gal85]. The classical string matching problem is to find all locations where a pattern string can be aligned with a text string such that the aligned characters of the pattern and the text match. Numerous variations of this p...