Suffix Trees
Compressed trie containing all suffixes of a string. O(n) nodes, O(m) pattern search, O(m+k) to find all k occurrences.
Key Properties
- Exactly n leaves (one per suffix), at most n-1 internal nodes
- Each internal node (except root) has >= 2 children
- Edge labels are substrings, not single characters
- Path from root to leaf i spells suffix starting at position i
Suffix Tree vs Suffix Array
| | Suffix Tree | Suffix Array | |---|---|---| | Space | O(n) but large consta
[Description truncada. Veja o README completo no GitHub.]