McCreight's Algorithm

McCreight's algorithm is a method for constructing a suffix tree, a compressed trie containing every suffix of a given string, that runs in time proportional to the length of the string for a fixed-size alphabet. Edward McCreight's method builds on an earlier suffix tree construction approach published by Peter Weiner, but simplifies it considerably, discarding most of Weiner's auxiliary bookkeeping structures and keeping only a mechanism called suffix links, pointers between related positions in the tree that let the algorithm skip repeated work as it inserts each new suffix; because a suffix's path through the compressed trie takes no more space than the identifying prefix used to construct it, the whole tree can be built and stored efficiently even though it represents every suffix of the input string. Edward M. McCreight published the algorithm in 1976 in a paper titled "A Space-Economical Suffix Tree Construction Algorithm" in the Journal of the ACM; Esko Ukkonen simplified suffix tree construction further in 1995 with an algorithm that, unlike McCreight's, builds the tree online, one character at a time, as the input string is read.