suffixtries

A suffix trie is a tree-based data structure that contains all suffixes of a given string. Each root-to-leaf path spells a suffix, and every substring of the string appears as a path that starts at the root and follows consecutive edges. Suffixes are stored so that shared prefixes are merged, meaning common beginnings of different suffixes share nodes.

It is typically built by inserting each suffix s[i:] of the string s into a trie. A naïve build inserts n suffixes, leading to up to n(n+1)/2 distinct prefixes and a worst-case space usage of O(n^2). The time to build is also O(n^2) in the worst case; strings with many repeated characters can reduce the number of nodes but the worst-case growth remains quadratic.

For pattern matching, a substring query is performed by traversing the trie from the root following the characters of the pattern. If all m characters can be followed, the pattern occurs in the string; the query time is O(m). This makes suffix tries straightforward for exact substring checks, but not space-efficient for large inputs.

Compared with related structures, suffix tries are space-inefficient for long strings. Suffix trees compress the trie’s edges to achieve O(n) nodes and edges, enabling linear-time substring queries with much smaller memory usage. Suffix arrays with longest common prefix arrays offer another compact approach to similar substring-search problems.

Applications include text searching, pattern matching, and educational contexts to illustrate trie-based indexing. In practice, suffix tries are often used as a conceptual stepping stone to more space-efficient structures. Variants include the compressed suffix trie (equivalent to a suffix tree) and the suffix automaton, which provide more compact representations and support for dynamic operations.