In computer science, a suffix 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 for the suffixes of . A suffix tree is a special kind of a Trie. 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. Wikipedia [ - ]

In computer science, a suffix tree is a data structure that presents the suffixes of a given... [ + ]