The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matchign, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for hte construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of sufffix trees: we give a las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take omiga(log sup 2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.
展开▼
