Structure
Every suffix ends at a leaf. Each edge labeled with a substring. Internal nodes have ≥ 2 children.
Advertisement
Space + time
O(N) size + O(N) construction via Ukkonen's algorithm. Complex but linear.
Advertisement
What it enables
- Substring search: O(P)
- LCS of two strings: O(N + M)
- Repeated substrings
- Longest palindromic substring