Abstract

Given a string S[1...n], the suffix selection problem is to find the k-th 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 Theta(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 Theta(n log n) comparisons, but does suffix selection need suffix sorting? Recent studies have addressed this fundamental problem. We present an optimal, deterministic algorithm for suffix selection using O(n) comparisons (and O(n) time).

Presentation files