Menu
Given a two-dimensional text \(T\) and a set of patterns \(\mathcal{D} = \{P_1, \ldots, P_k\}\) (the dictionary), the two-dimensional \emph{dictionary matching} problem is to determine all the occurrences in \(T\) of the patterns \(P_i \in \mathcal{D}\). The two-dimensional \emph{dictionary prefix-matching} problem is to determine the longest prefix of any \(P_i \in \mathcal{D}\) that occurs at each position in \(T\). Given an alphabet \(\Sigma\), an \(n \times n\) text \(T\), and a dictionary \(\mathcal{D} = \{P_1, \ldots, P_k\}\), we present an algorithm for solving the two-dimensional dictionary prefix-matching problem. Our algorithm requires \(O(|T| + |\mathcal{D}|(log m + log |\Sigma|))\) units of time, where \(m \times m$ is the size of the largest \(P_i \in \mathcal{D}\). The algorithm presented here runs faster than the Amir and Farach [3] algorithm for the dictionary matching problem by an \(O(log k)\) factor. Furthermore, our algorithm improves the time bound that can be achieved using the Lsuffix tree of Giancarlo [6],[7] by an \(O(k)\) factor.