Structure
Compressed trie. Each edge labeled with substring range. Internal nodes have ≥ 2 children. N+1 leaves (one per suffix).
Advertisement
Ukkonen ideas
Active point + remainder count. Suffix links speed up transitions. Skip/count trick amortizes.
Advertisement
Complexity
O(N) time, O(N) space. σ (alphabet) affects constant via child map choice.
Applications
Substring search: O(M). Longest common substring of K strings. Longest repeated substring. Palindrome finding.