What's the current state-of-the-art suffix array construction algorithm?

Currently, the best Suffix-Array constructor known is LibDivSufSort, by Yuta Mori : http://code.google.com/p/libdivsufsort/

It uses Induced Sorting methodology (Basically, after sorting all strings starting with "A*", you can induce sortings of strings "BA*" "CA*" "DA*" etc.)

It is praised everywhere for its efficiency and nice handling of degenerated cases. It's also the fastest, and uses the optimal amount of memory (5N). The license is unobstrusive, so this algorithm is integrated into several other programs, such as for example libbsc compression library, by Ilya Grebnov. http://libbsc.com/default.aspx

For comparison purposes, you will find a Suffix Array Compression benchmarks linked at this page : http://code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks and this page http://homepage3.nifty.com/wpage/benchmark/index.html

The benchmark also lists many other worthy SACA implementation. Nevertheless, for both license and efficiency reason, i would recommend libdivsufsort among them.

Edit : Apparently, MSufsort is said to be heading towards version 4 soon, and is supposed to become quite faster than Divsufsort. If that is right, it would become a new SACA champion. But still, we don't have release date yet, and this will be alpha stuff. So if you need a proven implementation now, libdivsufsort remains the best choice.

Note also that these "best SACA implementations" do not use "one construction algorithm", but combine several optimisations tricks, which makes them difficult to summarize.

https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md gives the list of fastest algorithms you want.

kvark's implementation is the fastest in most of case in the above benchmark. You can find the code on https://github.com/kvark/dark-archon.

libdivsufsort is a combination of Itoh-Tanaka's algorithm and the Induced Sorting's post process. A subset of suffixes is picked just like the induced sorting algorithm, but instead of recursively solve it by induced sorting, they are sorted by IT's algorithm.

libdivsufsort and kvark's implementation are both based on IT's algorithm.

Ko-Aluru's algorithm is similar to the IT's algorithm, which appears in 99. They both divide the suffixes into 2 categories: type S or type L. If the i-th suffix is smaller than the (i+1)-th suffix, it's type S; otherwise it's type L. After sorting all type S suffixes, we can deduce the order of all type L suffixes, then we're done.

The difference between KA's algorithm and IT's algorithm is that: KA use recursion to sort the substrings, while IT's algorithm appeals to Multikey Quicksort/MSD/insertion sort.

You could look at:

A quick tour on suffix arrays and compressed suffix arrays R Grossi - Theoretical Computer Science, 2011

Probably new suffix array algorithms are are no longer being developed at the pace you imagine. To be on the bleeding edge, I would suggest Looking at data structures that are used together with suffiix arrays and look at papers on suffix array-related mathematics: Schürmann, Munro, He etc