In-place suffix sorting

G. Franceschini, S. Muthukrishnan

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

25 Scopus citations

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 - Jan 1 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

Other

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

All Science Journal Classification (ASJC) codes

  • 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