27

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

Vinicius Braz Pinto
  • 8,209
  • 3
  • 42
  • 60
  • 5
    To anyone who finds this question: A similar one came up [here](http://stackoverflow.com/q/9452701/777186) and we are creating a description of the algorithm as a Stackoverflow answer [here](http://stackoverflow.com/a/9513423/777186). – jogojapan Mar 03 '12 at 01:18

1 Answers1

15

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.

Jouni K. Seppänen
  • 43,139
  • 5
  • 71
  • 100
  • 1
    Is there an animated version of this ukkonen algo? Sorry i couldn't understand the constant nature of "update" function. I tried gusfield, ukkonen's paper and google too :D – Seeker Sep 07 '10 at 03:55
  • 1
    I would love to watch a animation for building a generalized suffix tree in linear time. Generally text based explanation wont fit in my mind..:) – Abhi Jan 26 '12 at 00:07
  • 1
    Gusfields chapter on suffix trees has this annoying feature, that he uses different strings to illustrate the different steps - so you loose the big picture. – maasha Jun 26 '12 at 07:52
  • You can view an animation here http://brenden.github.io/ukkonen-animation/ – seahorse Jun 03 '18 at 06:59
  • The link is broken. Does anyone have an alternate? – Andrew Scott May 15 '19 at 09:49
  • I edited the link to point to Goodreads instead of Google Books. – Jouni K. Seppänen May 15 '19 at 14:04