Hacker News new | past | comments | ask | show | jobs | submit login
Ukkonen's suffix tree algorithm explained in plain English (stackoverflow.com)
76 points by axefrog on April 12, 2012 | hide | past | favorite | 3 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/




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: