TY - GEN

T1 - Optimal suffix selection

AU - Franceschini, Gianni

AU - Muthukrishnan, S.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Order statistics

KW - Selection

KW - Strings

KW - Suffixes

UR - http://www.scopus.com/inward/record.url?scp=35448977257&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448977257&partnerID=8YFLogxK

U2 - 10.1145/1250790.1250840

DO - 10.1145/1250790.1250840

M3 - Conference contribution

AN - SCOPUS:35448977257

SN - 1595936319

SN - 9781595936318

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 328

EP - 337

BT - STOC'07

T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing

Y2 - 11 June 2007 through 13 June 2007

ER -