Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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