Problem Detail: 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?
Asked By : Rontogiannis Aristofanis
Answered By : A.Schulz
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9447
