Optimal suffix tree construction with large alphabets

Martin Farach

    Research output: Contribution to journalConference articlepeer-review


    The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. Weiner, who introduced the data structure, gave an O(n)-time algorithm for building the suffix tree of an n-character string drawn from a constant size alphabet. In the comparison model, there is a trivial Ω(n log n)-time lower bound based on sorting, and Weiner's algorithm matches this bound trivially. For integer alphabets, a substantial gap remains between the known upper and lower bounds, and closing this gap is the main open question in the construction of suffix trees. There is no super-linear lower bound, and the fastest known algorithm was the O(n log n) time comparison based algorithm. We settle this open problem by closing the gap: we build suffix trees in linear time for integer alphabet.

    Original languageEnglish (US)
    Pages (from-to)137-143
    Number of pages7
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    StatePublished - 1997
    EventProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA
    Duration: Oct 20 1997Oct 22 1997

    ASJC Scopus subject areas

    • Hardware and Architecture


    Dive into the research topics of 'Optimal suffix tree construction with large alphabets'. Together they form a unique fingerprint.

    Cite this