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:
“To summarize the contentions of this paper then. Firstly, the phrase ‘the meaning of a word’ is a spurious phrase. Secondly and consequently, a re-examination is needed of phrases like the two which I discuss, ‘being a part of the meaning of’ and ‘having the same meaning.’ On these matters, dogmatists require prodding: although history indeed suggests that it may sometimes be better to let sleeping dogmatists lie.”
—J.L. (John Langshaw)
“It would be naive to think that peace and justice can be achieved easily. No set of rules or study of history will automatically resolve the problems.... However, with faith and perseverance,... complex problems in the past have been resolved in our search for justice and peace. They can be resolved in the future, provided, of course, that we can think of five new ways to measure the height of a tall building by using a barometer.”
—Jimmy Carter (James Earl Carter, Jr.)
“As I am, so shall I associate, and so shall I act; Caesar’s history will paint out Caesar.”
—Ralph Waldo Emerson (1803–1882)