Here  are the notes for Chapter 6. The whole document can be found HERE.


As mentioned earlier, Apostolico pointed out the “myriad of virtues” possessed by suffix trees. There are too many to go into detail on each. We will cover the most fundamental and useful ones, namely, the exact string matching problem, the longest common substring of two strings, the substring problem for a database of patterns and the DNA contamination problem. We refer the reader to the book of Gusfield and the references therein for an exhaustive list of the applications of suffix trees.

Go to top