Elsevier, Information and Computation, (285), p. 104818, 2022
Springer Verlag, Lecture Notes in Computer Science, p. 268-284
DOI: 10.1007/978-3-030-00479-8_22
2018 Data Compression Conference
Full text: Download
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 in the last 20 years. We obtain the suffix array construction algorithms that are optimal both in time and space for both integer alphabets and general alphabets. Concretely, we make the following contributions: 1. For integer alphabets, we obtain the first algorithm which takes linear time and uses only $O(1)$ workspace (the workspace is the space needed beyond the input string and the output suffix array). The input string may be modified during the execution of the algorithm, but should be restored upon termination of the algorithm. Our algorithm is easy to implement. Our C implementation of the algorithm requires only 8 Bytes of workspace. 2. We strengthen the first result by providing the first linear time in-place algorithm for read-only integer alphabets (i.e., we cannot modify the input string $T$). This settles the open problem posed by Franceschini and Muthukrishnan in ICALP 2007 \cite{franceschini2007place}. 3. For read-only general alphabets (i.e., only comparisons are allowed), we present an in-place $O(n\log n)$ time algorithm, recovering the result obtained by Franceschini and Muthukrishnan \cite{franceschini2007place}. ; Comment: 32 pages