Abstract

There are several serial algorithms for suffix tree construc- tion which run in linear time, but the number of operations in the only parallel algorithm available, due to Apostolic, Iliopoulos, Landau, Schieber and VLshkin, is proportional to n log n. The algorithm is based on labeling substringsj sim- ilar to a classical serial algorithm, with the same operations bound, by Karp, Miller and Rosenberg. We show how to break symmetries that occur in the process of assigning la- bels using the Deterministic Coin Tossing (DCT) technique, and thereby reduce the number of labeled substrings to lin- ear. We give several algorithms for suffix tree construction. One of them runs in O(log^2 n) parallel time and O(n) work for input strings whose characters are drawn from a constant size alphabet.