suffixtrees

A suffix tree is a data structure that represents all suffixes of a given string as paths from a common root in a compressed trie. Edges are labeled with substrings of the string, and each suffix S[i..n] corresponds to a leaf. Internal nodes correspond to substrings that occur as prefixes of several suffixes. The tree enables efficient substring queries and pattern matching.

In a suffix tree, every internal node has at least two children, and edges are labeled with nonempty substrings. The concatenation of edge labels along a root-to-leaf path spells a suffix of the string. A concept called suffix links connects nodes representing substrings that share a suffix when the first character is removed, which helps in fast construction. The tree typically contains O(n) nodes and O(n) edges for a string of length n, and can be built for a single string or generalized to handle multiple strings.

Construction and complexity: The classic online construction uses Ukkonen’s algorithm, which builds a suffix tree in linear time, O(n), for a string of length n. A naive approach that inserts all suffixes can take O(n^2) time. The data structure requires O(n) space. Generalizations exist for sets of strings, yielding generalized suffix trees, and variants support circular strings or dynamic updates.

Applications: Suffix trees enable fast substring search in O(m) time for a pattern of length m, by locating the corresponding locus in the tree and reporting all occurrences. They support operations such as finding the longest repeated substring, counting distinct substrings, and locating all positions where a pattern occurs. They are widely used in bioinformatics, text search, and data compression, though suffix arrays offer a more space-efficient alternative with similar capabilities.