Optimal suffix selection

Gianni Franceschini, S. Muthukrishnan

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

    Abstract

    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
    Pages328-337
    Number of pages10
    DOIs
    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

    Other

    OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
    CountryUnited States
    CitySan Diego, CA
    Period6/11/076/13/07

    Keywords

    • Order statistics
    • Selection
    • Strings
    • Suffixes

    ASJC Scopus subject areas

    • Software

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

  • Cite this

    Franceschini, G., & Muthukrishnan, S. (2007). Optimal suffix selection. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 328-337). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250840