Suffix Trees Trimmed

The Suffix Tree is a beautiful data structure. It encodes O(n^2) total size of substrings of a string of length n in an O(n) sized tree, and can be constructed in O(n) time. It was invented by Peter Wiener in 1973 and is one of the earliest, nontrivial sub-sorting time algorithms. Now there are half a dozen or more linear time algorithms for constructing suffix trees including the big breakthrough of Martin Farach Colton's in mid 90's that this could be done even for integer sized alphabets.

Combinatorial Pattern Matching (CPM) 2013 celebrated the 40th anniversary of this remarkable invention.  Amazing galaxy of speakers --- Vaughan Pratt, Peter Weiner, Ed McCreight, Martin Farach-Colton, Jacob Ziv --- onstage!  Check out the video channel of talks.  Incredible window into the history of (string) algorithms, including a referee's perspective. Of course, Vaughan Pratt is an extraordinary referee. See more details about the event here. There is a research paper on Forty Years of Text Indexing, in the proceedings.