History
The concept was first introduced as a position tree by Weiner (1973), which Donald Knuth subsequently characterized as "Algorithm of the Year 1973". The construction was greatly simplified by McCreight (1976), and also by Ukkonen (1995). Ukkonen provided the first online-construction of suffix trees, now known as Ukkonen's algorithm, with running time that matched the then fastest algorithms. These algorithms are all linear-time for a constant-size alphabet, and have worst-case running time of in general.
Farach (1997) gave the first suffix tree construction algorithm that is optimal for all alphabets. In particular, this is the first linear-time algorithm for strings drawn from an alphabet of integers in a polynomial range. Farach's algorithm has become the basis for new algorithms for constructing both suffix trees and suffix arrays, for example, in external memory, compressed, succinct, etc.
Read more about this topic: Suffix Tree
Famous quotes containing the word history:
“I believe my ardour for invention springs from his loins. I can’t say that the brassiere will ever take as great a place in history as the steamboat, but I did invent it.”
—Caresse Crosby (1892–1970)
“Humankind has understood history as a series of battles because, to this day, it regards conflict as the central facet of life.”
—Anton Pavlovich Chekhov (1860–1904)
“Both place and time were changed, and I dwelt nearer to those parts of the universe and to those eras in history which had most attracted me.”
—Henry David Thoreau (1817–1862)