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: http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Com... 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.
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: http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Com... 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.