Multidimensional matching and fast search in suffix trees
Richard J. Cole, Moshe Lewenstein · 2003
Abstract We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension. 1 Introduction.As is well known, suffix trees can be built in linear time [12, 13, 6]. However, the searches on the resulting tries may face branches of degree equal to the alphabet size. One approach represents these choices using a tree of height log \\Sigma, potentially raising the cost of a search to \\Theta (p log \\Sigma). A second approach uses a hash table at each node, but the known linear time algorithms for building such hash tables are randomized. A third approach, due to Breslauer [4], achieves search time O(p + log t) but at the cost of an O(t log \\Sigma) construction time. We improve the construction time to O(t) time for polynomial range alphabets. This thereby matches the performance of suffix arrays [11]. Bird [3] and Baker [2] showed how to reduce ddimensional pattern matching to d iterations of onedimensional dictionary matching, with dictionaries of md\\Gamma 1 words each m characters long. The resulting algorithm had complexity O((nd+md) log m). Breslauer improved this result to O(nd + md log m) using a table of size O(md+ffl), which with the use of hashing can be reduced to O(md) (using randomization). We improve the time bound to O(nd +md) using space O(md). This bound was already known in two dimensions based on two-dimensional periodicity [1, 7] which is not needed here.