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_algorithmI 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.
