suffix tree

(data structure)

Definition: A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents.

Generalization (I am a kind of ...)
Patricia tree, trie.

Specialization (... is a kind of me.)
multi suffix tree.

Note: A suffix tree is a Patricia tree corresponding to the suffixes of a given string. A directed acyclic word graph (DAWG) is a more compact form.

Author: SE

Implementation

Strmat - a variety of string matching and pattern discovery algorithms (C) (C++ and Pascal).

More information

Explanations of and comparisons between tries and suffix trees.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Tue Jan 4 10:47:14 2005.
HTML page formatted Wed Oct 26 09:48:14 2005.

Cite this as:
Stefan Edelkamp, "suffix tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/suffixtree.html