Abstract

Suffixtreesare the main data-structurein stringmatching algorithmics. There areseveralserialalgorithms forsuffixtreeconstructionwhich run inlineartime,but the number of operations in the only parallelalgorithm available,due to Apostolico, Iliopoulos,Landau,SchieberandVishkin,isproportionaltonlogn. Thealgorithm is based on labeling substrings, similar 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 labels using the Deterministic Coin Tossing (DCT) technique, and thereby reduce the number of labeled substrings to linear.