Parallel construction of a suffix tree with applications

A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, U. Vishkin

Research output: Contribution to journalArticlepeer-review

125 Scopus citations


Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string of n symbols in O(log n) time with n processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced to O(n 1+e{open}) for any 0< e{open} ≤1, with a corresponding slow-down proportional to 1/e{open}. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.

Original languageEnglish (US)
Pages (from-to)347-365
Number of pages19
Issue number1-4
StatePublished - Nov 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Approximate string matching
  • Longest repeated substring in a string
  • On-line string matching
  • Parallel algorithms
  • Processor allocation techniques
  • Skeleton trees
  • Suffix trees


Dive into the research topics of 'Parallel construction of a suffix tree with applications'. Together they form a unique fingerprint.

Cite this