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.

The newer suffix array has replaced the suffix tree as the data structure of choice in many applications.

Author: SE

Implementation

Strmat - a variety of string matching and pattern discovery algorithms (C). Christian Kreibich's libstree (C) including depth- and breadth-first traversal, string update, and examples like LCS. Mark Nelson's great Fast String Searching With Suffix Trees (C++) explains Ukkonen's linear-time algorithm. Dr. Dobb's Journal, August, 1996. Steven Skiena's Suffix Trees and Arrays (C++, Python, and Java).

More information

Edward M. McCreight, A space-economical suffix tree construction algorithm, Journal of the ACM, 23:262-272, 1976.

Esko Ukkonen, On-line construction of suffix trees, Algorithmica, 14(3):249-260, September 1995.
A linear time, forward construction algorithm. See Wikipedia entry for links to PDF of Ukkonen's paper.

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

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

Entry modified 29 November 2021.
HTML page formatted Mon Nov 29 08:59:33 2021.

Cite this as:
Stefan Edelkamp, "suffix tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 29 November 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/suffixtree.html