ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1517. Freedom of Choice

Suffix tree construction
Posted by Giorgi Saghinadze (Tbilisi SU) 12 Nov 2007 15:55
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.
Re: Suffix tree construction
Posted by Rafail Ahmadisheff 27 Jan 2008 02:47
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.
Re: Suffix tree construction
Posted by svr 6 Feb 2008 17:42
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.
Thank you! (-)
Posted by Rafail Ahmadisheff 16 Feb 2008 23:35