TCS-TR-A-06-19Date: Tue Jul 18 22:56:52 2006 Authors: Hiroki Arimura and Takeaki Uno Contact:
Abstract. In this paper, we consider the problem of finding maximal patterns in an two-dimensional text for the class of two-dimensional picure patterns with wild cards (don't cares). A maximal pattern for two-dimensional text is a generalization of a 1-dimensional sequential motif in (Parida et al., SODA'00; Pisanti et al., MFCS'03; Pelfrene etal., CPM'03), and it is such a representative pattern that is not properly contained in any larger pattern with the same location lists under invariance with respect to parallel motion. Since a text may contain exponentially many maximal patterns in general, it is natural to consider an output-sensitive algorithms for enumerating all patterns in the class. Then, we present a polynomial space and polynomial delay algorithm for enumerating all maximal patterns in a text array in exact polynomial time per discovered pattern in the total size of the input text. This result is achieved by backtracking through depth-first search of a tree-shaped search route over all maximal patterns, similar to (Arimura et al., ISAAC'05). We also discuss the lowerbound results on the number of maximal patterns and the #P-hardness of conting, and efficient input polynomial time computation of constant patterns with matrix suffix trees. ©Copyright 2006 Authors |