Understanding Ukkonen's algorithm for suffix trees

Question

Hello,

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 1

Very interesting algorithm, I'll definitely study it.

Check out these 2 links I found for some insights,

• Fast String Searching With Suffix Trees
• Suffix Trees

Answer 2

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.