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:
“The history of men’s opposition to women’s emancipation is more interesting perhaps than the story of that emancipation itself.”
—Virginia Woolf (1882–1941)
“The history of progress is written in the blood of men and women who have dared to espouse an unpopular cause, as, for instance, the black man’s right to his body, or woman’s right to her soul.”
—Emma Goldman (1869–1940)
“Boys forget what their country means by just reading “the land of the free” in history books. Then they get to be men, they forget even more. Liberty’s too precious a thing to be buried in books.”
—Sidney Buchman (1902–1975)