📖 WHAT IS A TRIE???!
A Trie (from “retrieval”, pronounced “try” for some reason) is a tree where each path from the root to a node spells out a string. Tries are also called prefix trees.
A Suffix Trie is built by inserting every suffix of a string S into a single trie. The resulting structure can answer “is P a substring of S?” in O(|P|) time — just walk from the root following the characters of P.
The catch? A suffix trie has O(n²) nodes for a string of length n. That memory cost motivated compressed suffix trees (Patricia tries) and the even more compact Directed Acyclic Word Graph (DAWG).
🧠 Key Concepts
- Trie Node
- Each node represents one character on a path from the root. The root is the empty string.
- Edge Label
- Every edge carries exactly one character. Following a path from the root spells a string.
- Suffix
- A suffix of “abc” is any of: “abc”, “bc”, “c”. A suffix trie inserts all of them.
- Leaf Node
- A node marked with a double ring — it signals the end of an inserted suffix.
- Substring Search
- To check if P is a substring of S, follow the characters of P from the root. If every step succeeds, P is a substring!
⚙️ ENTER YOUR WORD!!!
Type a short word (2–25 lowercase letters). We will build the Suffix Trie for it step by step!