In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a data structure that presents the suffixes of a given string in a way that allows for a particularly fast implementation of many important string operations.
The suffix tree for a string is a tree whose edges are labeled with strings, such that each suffix of corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree (more specifically, a Patricia tree) for the suffixes of .
Constructing such a tree for the string takes time and space linear in the length of . Once constructed, several operations can be performed quickly, for instance locating a substring in, locating a substring if a certain number of mistakes are allowed, locating matches for a regular expression pattern etc. Suffix trees also provided one of the first linear-time solutions for the longest common substring problem. These speedups come at a cost: storing a string's suffix tree typically requires significantly more space than storing the string itself.
Read more about Suffix Tree: History, Definition, Generalized Suffix Tree, Functionality, Applications, Implementation, External Construction
Famous quotes containing the word tree:
“A tree is made to live in peace in the color of day and in friendship with the sun, the wind and the rain. Its roots plunge in the fat fermentation of the soil, sucking in its elemental humors, its fortifying juices. Trees always seem lost in a great tranquil dream. The dark rising sap makes them groan in the warm afternoons. A tree is a living being that knows the course of the clouds and presses the storms because it is full of birds’ nests.”
—Jacques Roumain (1907–1945)