Suffix Tries and Suffix Trees

A suffix trie contains all suffixes of a string.

For "banana":

• banana
• anana
• nana
• ana
• na
• a

This approach enables $O(P)$ substring search (where $P$ is pattern length): a pattern exists in the string if and only if it's a prefix of some suffix.

Problem: suffix trie has $O(n^2)$ nodes for a string of length $n$. Suffix trees compress the suffix trie, reducing space to $O(n)$.

They enable:

• Substring search in $O(P)$
• Finding longest repeated substring
• Finding longest common substring of two strings

Building suffix trees efficiently (Ukkonen's algorithm) is complex. In competitive programming, simpler approaches often suffice.