C++ implementation of Ukkonen's Suffix Tree Construction Algorithm
A very fast linear time suffix tree construction algorithm is elaborately presented by Ukkonen. I like it so much. :-) I give my source codes of a C++ implementation here, under GPL license. Actually, many parts are borrowed from ANSI C Implementation.
What's interesting is the comparison between the C implementation and mine. I compiled both on my debian linux box using gcc 3.3. Without optimization, mine is about half slower than C. With -O3 for both, surprisely enough to me, mine is a bit faster than the C implementation. I like it. :-)
prerequisite software
libpoptTo compile
g++ treekits.cpp spattern.cpp -lpopt
enjoy it.
4 comments:
I'm working too on suffix trees but have an idea about how to alter a suffix tree to a generalized suffix tree with Ukkonen's algorithm, because i have found difficulties to understand Ukkonen's algorithm.
I also found Ukkonen's algorithm a bit difficult particularly using of suffix link and the trick to use it linear time. Can you provide a tutorial on this. It may be helpful for me
Hello Li Zhao,
The link to your code is broken. Can you fix it?
Thanks!
sorry, Andres
It is hosted by google pages, which stopped its service.
I have no backup of these files.
Post a Comment