A suffix trie contains all suffixes of a string.
For "banana":
- banana
- anana
- nana
- ana
- na
- a
This approach enables substring search (where is pattern length): a pattern exists in the string if and only if it's a prefix of some suffix.
Problem: suffix trie has nodes for a string of length . Suffix trees compress the suffix trie, reducing space to .
They enable:
- Substring search in
- 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.