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.