A Failure Function for Multiple Two-dimensional Pattern Matching

Abstract

Given a two-dimensional text $T$ and a set of patterns $\mathcal{D}=\{P_1,\dots ,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 $\mathrm{\Sigma }$, an $n\times n$ text $T$, and a dictionary $\mathcal{D}=\{P_1,\dots ,P_k\}$, we present an algorithm for solving the two-dimensional dictionary prefix-matching problem. Our algorithm requires $O(|T|+|\mathcal{D}|(logm+log|\mathrm{\Sigma }|))$ units of time, where $m\times m\$isthesizeofthelargest\text{(}{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(logk)$ 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.