Optimal logarithmic time randomized suffix tree construction

Martin Farach, S. Muthukrishnant

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix 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 Ω(log2 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.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
    EditorsFriedhelm Meyer auf der Heide, Burkhard Monien
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)3540614400, 9783540614401
    StatePublished - 1996
    Event23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 - Paderborn, Germany
    Duration: Jul 8 1996Jul 12 1996

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Optimal logarithmic time randomized suffix tree construction'. Together they form a unique fingerprint.

    Cite this