Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2018

Abstract

The suffix array is a fundamental data structure for many applications that involve string searching and data compression. Designing time/space-efficient suffix array construction algorithms has attracted significant attentions and considerable advances have been made for the past 20 years. We obtain the first in-place linear time suffix array construction algorithms that are optimal both in time and space for (read-only) integer alphabets. Our algorithm settles the open problem posed by Franceschini and Muthukrishnan in ICALP 2007. The open problem asked to design in-place algorithms in $o(n \log n)$ time and ultimately, in $O(n)$ time for (read-only) integer alphabets with $|\Sigma| \leq n$. Our result is in fact slightly stronger since we allow $|\Sigma| = O(n)$. Besides, we provide an optimal in-place $O(n \log n)$ time suffix sorting algorithm for read-only general alphabets (i.e., only comparisons are allowed), recovering the result obtained by Franceschini and Muthukrishnan which was an open problem posed by Manzini and Ferragina in ESA 2002.

Keywords

Suffix sorting, Suffix array, In-place

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Publication

Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE 2018), Lima, Peru, October 9-11

First Page

268

Last Page

284

ISBN

978-3-030-00478-1

Identifier

10.1007/978-3-030-00479-8_22

Publisher

Springer

City or Country

Cham

Additional URL

https://doi.org/10.1007/978-3-030-00479-8_22

Download

Share

COinS