Optimal suffix selection
Gianni Franceschini, Subramanian Muthukrishnan · 2007
Given a string S[1·s n], the suffix selection problemis to find the kth lexicographically smallest amongst the n suffixes S[i·s n], for i=1,...,n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes.