Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets

Suffix arrays and LCP arrays are one of the most fundamental data structures widely used for various kinds of string processing. Many problems can be solved efficiently by using suffix arrays, or a pair of suffix arrays and LCP arrays. In this paper, we consider two problems for a string of length $N$, the characters of which are represented as integers in $[1, \dots, \sigma]$ for $1 \leq \sigma \leq N$; the string contains $\sigma$ distinct characters, (1) construction of the suffix array and (2) simultaneous construction of both the suffix array and the LCP array. In the word RAM model, we propose algorithms to solve both the problems in $O(N)$ time using $O(1)$ extra words, which are optimal in time and space. Extra words mean the required space except for the space of the input string and output suffix array and LCP array. Our contribution improves the previous most efficient algorithm that runs in $O(N)$ time using $\sigma+O(1)$ extra words for the suffix array construction proposed by [Nong, TOIS 2013], and it improves the previous most efficient solution that runs in $O(N)$ time using $\sigma + O(1)$ extra words for both suffix array and LCP array construction using the combination of [Nong, TOIS 2013] and [Manzini, SWAT 2004]. Another optimal time and space algorithm to construct the suffix array was proposed by [Li et al, arXiv 2016] very recently and independently. Our algorithm is simpler than theirs, and it allows us to solve the second problem in optimal time and space.