Fast and Space Efficient Linear Suffix Array Construction

Abstract

Let S be an n-character string terminated with an unique smallest sentinel, its suffix array SA(S) is an array of pointers for all the suffixes in S sorted in the lexicographically ascending order. Specially, the Burrows-Wheeler transform for building efficient compression solutions can be quickly computed by fast suffix sorting based on suffix array construction algorithms (SACAs). The existing well-known practical linear SACAs are those two contemporarily reported in 2003 by Karkkainen and Sanders (KS) (J. Karkkaiinen and P. Sanders, 2003) and Ko and Aluru (KA) (P. Ko and S. Aluru, 2003).