# Algorithm for building a suffix array in time $O(n \log^2 n)$

I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand. I have seen in many sites that there is an $O(n \log^2 n)$ algorithm, but I can't understand it, as many important details are omitted. There's an example at Top Coder.

Could someone introduce me an efficient algorithm for suffix array construction, which is easy to comprehend?

-

You can compute the suffix array in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. The source code is contained in the original paper. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can also get the suffix-tree in linear time when you have access to the suffix-array and the LCP-array. The LCP-array can be also constructed with the DC3-algorithm.

-

Here's a good explanation for the $O(n\log^2n)$ algorithm: http://www.stanford.edu/class/cs97si/suffix-array.pdf. Actually, by using linear time sorting, the same approach gives $O(n\log n)$ time complexity.

If you have any specific question about it, you're welcome to ask.

I agree with A. Schultz that DC-3 is super-cool. It is also not very complicated, but the $O(n\log^2 n)$ is still simpler.

-