In-place suffix sorting

G. Franceschini, S. Muthukrishnan

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

    Abstract

    Given string T = T[1,... ,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,... ,n] for all i. This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of workspace needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant c in the O(n) = cn space algorithms known for this problem, Currently the best previous result [5] takes O (nv + n log n) time and O (n/ √v) extra space, for any v ∈6 [1, √n] for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes O (n log n) time using O(1) workspace and is optimal in the worst case for the general alphabet.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings
    PublisherSpringer Verlag
    Pages533-545
    Number of pages13
    ISBN (Print)3540734198, 9783540734192
    DOIs
    StatePublished - 2007
    Event34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland
    Duration: Jul 9 2007Jul 13 2007

    Publication series

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

    Conference

    Conference34th International Colloquium on Automata, Languages and Programming, ICALP 2007
    CountryPoland
    CityWroclaw
    Period7/9/077/13/07

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'In-place suffix sorting'. Together they form a unique fingerprint.

    Cite this