Here are the notes for Chapter 4. The whole document can be found HERE.
Sometimes fundamental techniques do not make it into the mainstream of computer science education in spite of its importance, as one would expect. Suffix trees is the perfect case in point. As Apostolico expressed it, suffix trees possess “myriad of virtues.” Nevertheless, even elementary texts on algorithms, such as that of Cormen, Aho or Sedgewick present brute-force algorithms to build suffix trees, notable exceptions being the book of Gusfield. That is a strange fact as much more complicated algorithms than linear construction of suffix trees are found in many computer science curricula. The two original papers that put forward the first linear-time algorithms have a reputation of being obscure and that might have contributed to this situation. In the following, we will try to give a clear and thorough explanation of their construction.
