Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
