Understanding Ukkonen's algorithm for suffix trees

algorithm complexity-theory suffix-tree
Vinicius Pinto picture Vinicius Pinto · Aug 20, 2009 · Viewed 8.1k times · Source

I'm doing some work with Ukkonen's algorithm for building suffix trees, but I'm not understanding some parts of the author's explanation for it's linear-time complexity.

I have learned the algorithm and have coded it, but the paper which I'm using as the main source of information (linked bellow) is kinda confusing at some parts so it's not really clear for me why the algorithm is linear.

Any help? Thanks.

Link to Ukkonen's paper: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Answer

Jouni K. Seppänen picture Jouni K. Seppänen · Aug 29, 2009

Find a copy of Gusfield's string algorithms textbook. It's got the best exposition of the suffix tree construction I've seen. The linearity is a surprising consequence of a number of optimizations of the high-level algorithm.

Related questions

How is it possible to build a suffix tree in linear time?

To build a suffix tree, in the worst case if all the letter of the string are different the complexity would be something like n + (n-1) + (n-2) ... 1 = n*(n+1)/2 which is O(n^2). However according to http://en.wikipedia.org/…

Read More
How to find time complexity of an algorithm

The Question How to find time complexity of an algorithm? What have I done before posting a question on SO ? I have gone through this, this and many other links But no where I was able to find a clear …

Read More
What is a plain English explanation of "Big O" notation?

I'd prefer as little formal definition as possible and simple mathematics.

Read More