### 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 - Oct 30 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 |
---|

### 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 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Order statistics
- Selection
- Strings
- Suffixes

### 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

}

*STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing.*Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 328-337, STOC'07: 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, United States, 6/11/07. https://doi.org/10.1145/1250790.1250840

**Optimal suffix selection.** / Franceschini, Gianni; Muthukrishnan, Shan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimal suffix selection

AU - Franceschini, Gianni

AU - Muthukrishnan, Shan

PY - 2007/10/30

Y1 - 2007/10/30

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 - https://doi.org/10.1145/1250790.1250840

DO - https://doi.org/10.1145/1250790.1250840

M3 - Conference contribution

SN - 1595936319

SN - 9781595936318

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

SP - 328

EP - 337

BT - STOC'07

ER -