Optimal suffix selection

Gianni Franceschini, S. Muthukrishnan

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

4 Scopus citations


Given a string S[1 ⋯ n], the suffix selection problem is to find the kth lexicographically smallest amongst the n suffixes S[i ⋯ n], for i = 1, . . . , n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisons and the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Number of pages10
StatePublished - 2007
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Software


  • Order statistics
  • Selection
  • Strings
  • Suffixes


Dive into the research topics of 'Optimal suffix selection'. Together they form a unique fingerprint.

Cite this