7
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.