Symmetry breaking for suffix tree construction
- 1 January 1994
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 300-309
- https://doi.org/10.1145/195058.195164
Abstract
There are several serial algorithms for suffix tree constructionwhich run in linear time, but the number of operationsin the only parallel algorithm available, due to Apostolico,Iliopoulos, Landau, Schieber and Vishkin, is proportional ton log n. The algorithm is based on labeling substrings, similarto a classical serial algorithm, with the same operationsbound, by Karp, Miller and Rosenberg. We show how tobreak symmetries that occur in the process of assigning labelsusing the...Keywords
This publication has 0 references indexed in Scilit: