### 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 language | English (US) |
---|---|

Title of host publication | STOC'07 |

Subtitle of host publication | Proceedings of the 39th Annual ACM Symposium on Theory of Computing |

Pages | 328-337 |

Number of pages | 10 |

DOIs | |

State | Published - 2007 |

Event | STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | San Diego, CA |

Period | 6/11/07 → 6/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

*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