1995 | ReviewPaper | Chapter
Two-dimensional pattern matching in linear time and small space
Extended abstract
Authors : Maxime Crochemore, Leszek Gasieniec, Wojciech Rytter, Wojciech Plandowski
Published in: STACS 95
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present the first known (alphabet independent) algorithm for two-dimensional pattern matching which works in linear time and small space simultaneously. The searching phase of our algorithm works in O(1) space and is followed by pattern preprocessing performed in O(logm) space. Up to now there was not known even any efficient sublinear space algorithm for this problem. The main tools in our algorithm are several 2-dimensional variations of deterministic sampling, originally used in parallel pattern matching: small, frame and wide samples. Another novel idea used in our algorithm is the technique of zooming sequences: the sequences of nonperiodic decreasing parts of the pattern (samples) of similar regular shapes. Their regularity allows to encode the zooming sequences in small memory (logarithmic number of bits) while nonperiodicity allows to make shifts (kill positions as candidates for a match) in a way amortizing the work. The preprocessing phase is recursive, its structure is similar to the linear time algorithm for the selection problem. The stack of the recursion consists of logarithmic number of integers. Our algorithm is rather complicated, but all known alphabet-independent linear time algorithms (even with unrestricted space) for 2d-matching are quite complicated, too.