## 2 Background
[PERSON] and [PERSON] [10] also used recursive partitioning, but following a fundamentally different approach to construct the suffix array in linear space and linear time. They use a binary marking strategy whereby each suffix in \(T\) is classified as either an \(S\)-suffix or an \(L\)-suffix, depending on its relative order with its next neighbor. Let \(T^{\prime}_{i}=t_{i}t_{i+1}t_{i+2}\ldots t_{n-1}\) denote the suffix \(T^{\prime}_{i}\) of sequence \(T\) starting at position \(i\). An \(S\)-suffix is a suffix that is lexicographically smaller than its right neighbor in \(T\), while an \(L\)-suffix is one that is lexicographically larger than its right neighbor. That is, \(T^{\prime}_{i}\) is an \(S\)-suffix if \(T^{\prime}_{i}\prec T^{\prime}_{i+1}\), otherwise \(T^{\prime}_{i}\) is an \(L\)-suffix. This classification is motivated by the observation that an \(S\)-suffix is always lexicographically greater than any \(L\)-suffix that starts with the same first character. The two types of suffixes are then treated differently, whereby the \(S\)-suffixes are sorted recursively by performing some special distance computations. The \(L\)-suffixes are then sorted using the sorted order of the \(S\)-suffixes. The classification scheme is very similar to the approach earlier used by [PERSON] and [PERSON] [19]. But the algorithm in [19] runs in \(O(n\log n)\) time on average. Lightweight suffix sorting algorithms [3; 17; 20; 21] have also been proposed which pay more attention on the extra working space required. Working space excludes the space for the output suffix array. In general, the suffix array requires \(n\lceil\log n\rceil\) bit space, while the input text requires another \(n\lceil\log|\Sigma|\rceil\) bits, or in the worst case \(n\lceil\log n\rceil\) bits. In [22], an algorithm that runs in \(O(n\log n)\) worst case time, requiring \(O(n\log n+(n/\sqrt{\log n}))\) working space was proposed, while [PERSON] _et al._[20] constructed suffix arrays for integer alphabets in \(O(n\log n)\) time, using \(O(n\log n)\)-bit space. [PERSON] and [PERSON] [17] combined ideas from the KS algorithm [9] and the KA algorithm [10] to develop a method that works in \(O(n\log|\Sigma|)\) time, using \((n\log|\Sigma|+|\Sigma|\log n)\)-bit working space (without the output suffix array). In [23; 24] they extended the method to use \(2n+O(1)\) bytes of working space (or a total space of \(7n+O(1)\) bytes, including space for the suffix array, and the original sequence), by exploiting special properties of the \(L\) and \(S\) suffixes used in the KA algorithm, and of the leftmost \(S\)-type substrings. In-place suffix sorting was considered in [25], where suffix sorting was performed for strings with symbols from a general alphabet using \(O(1)\) working space in \(O(n\log n)\) time. In some other related work [2; 26], computing the BWT was viewed as a suffix sorting problem. [PERSON] and [PERSON] [26] modified a suffix sorting algorithm to compute the BWT using a working space of \(O(n\log|\Sigma|\log\log_{|\Sigma|}n)\) bits. There has also been various efforts on compressed suffix arrays and compressed suffix trees as a means to tackle the space problem with suffix trees and suffix arrays. (See [27; 28; 29] for examples). We do not consider compressed data structures in this work. A detailed survey on suffix array construction algorithms is provided in [4].