Found in 2 comments on Hacker News
ahelwer · 2012-04-12 · Original thread
I've not read that textbook, but another excellent text is "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield ( 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.

mayank · 2010-10-26 · Original thread
All very nice suggestions below, but I found suffix trees missing:

And the reasons why it blows my mind:

(1) Knuth called it "Algorithm of the year 1973" (possibly because it beat an intuitive lower bound that he had for a problem I can't remember).

(2) It's relatively new for a "core", first-principles algorithm. Ukkonen's algorithm is from 1995, although there are earlier versions.

(3) This BOOK is largely devoted to the many, many applications of suffix trees: It should be required reading for anyone interested in advanced algorithms.

(4) Longest common substring in linear time.

(5) Lempel-Ziv decomposition in linear time.

(6) Longest repeated substrings in linear time.

And too many more to list.

Fresh book recommendations delivered straight to your inbox every Thursday.