How to construct suffix tree in N*log(N) time? I am searching it in internet for 2 days and can't find site where all will be explained clearly. If you now link where suffix tree constuction algorithm is explained clearly give me please. thanks.
Actually, you'll find it possible to construct a Suffix Tree in O(N) (-: First such algo was offered by Weiner in 1973. Some new ideas have sprung to life since then. I believe, nowadays Ukkonen's algorithm for online suffix tree construction is your best choice for most applications. http://en.wikipedia.org/wiki/Ukkonen's_algorithm I personally tried a pair of its implementations: 1) Using explanation by Lloyd Allison ( http://www.allisons.org/ll/AlgDS/Tree/Suffix/ ) and implementation by Stephan T. Lavavej ( http://nuwen.net/libnuwen.html ) as base, I coined some C++ code... It got TLE 12. 2) Then I considered Dan Gusfield's book "Algorithms on Strings, Trees and Sequences" (Strictly speaking, I was reading Russian translation by Romanovsky - if it matters). And, you know, they made some sample programs in C available online ( http://www.cs.ucdavis.edu/~gusfield/strmat.html ) TLE 10 was the best judgement result I ever saw on this attempt.
I finally solved the problem with DAWGs (also known as Suffix Automata). This time I referred to "Automata for Matching Patterns" by Maxime Crochemore and Christophe Hancart for ideas, proofs and samples all along ( http://www-igm.univ-mlv.fr/~mac/REC/B4.html ). AC in 0.125 s.
Thus I got disappointed with Suffix Trees: despite them being good for theoretical considerations, in practice I'd rather be using Suffix Automata from now on.
In this problem there is a big another problem: Create rather many triks to implement suffix tree maximally compact, because test were very optimized by authors. For example such structure as vector is unsatisfactory for description of adjast list in each node. I were forced to organize dynamic memory allocation by small parts for each new edge in int *smeg with rewriting stored information.