Ukkonen's suffix tree algorithm explained in plain English

stackoverflow.com

76 pointsaxefrog3 comments

For those who want to learn more about this kind of algorithms on strings, there is a great book named, unsurprisingly, "Algorithms on Strings" (http://www.amazon.com/Algorithms-Strings-Maxime-Crochemore/d...).

Although I must admint, jogojapan has written a really clear and thoughtful explanation of Ukkonen's algorithm on stackoverflow, the best one I've ever read.

I've not read that textbook, but another excellent text is "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield (http://www.amazon.ca/Algorithms-Strings-Trees-Sequences-Comp...). It has a strong bioinformatics leaning, so you learn all sorts of interesting near-real-world applications for the algorithms.

Starts off talking about all the standard exact pattern matching algorithms, then moves on to suffix trees, then inexact matching, then finishes off with some advanced topics (that I have not read yet). Anyway, I'm really enjoying reading it and definitely recommend it.

For anyone (like me) that isn't familiar with what this would be used for should have a look at the first link the Stack Overflow OP references: http://marknelson.us/1996/08/01/suffix-trees/

Reply on news.ycombinator.com