Hello Codeforces!
Building a Suffix Automaton (SAM) for a single string is a classic linear-time algorithm. Extending it to a set of strings (a Trie) is also common, known as a Generalized Suffix Automaton (GSAM). However, most standard implementations for GSAM are done offline (usually using BFS) to preserve the $$$O(N)$$$ time complexity. For a deep mathematical analysis of the standard offline construction and space bounds, you can refer to this paper: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35395.pdf
But what if the problem forces us to build the SAM on a Trie strictly online?
If we blindly apply the standard SAM construction online on a Trie, the amortized complexity analysis breaks. The cloned states and suffix link redirections can force us to traverse long paths repeatedly, blowing the complexity up to $$$O(N^2)$$$ in the worst case (imagine a star-shaped Trie or multiple branches sharing the same suffix paths).
In this tutorial, I will share a powerful technique to maintain a Dynamic SAM on a Trie strictly online in amortized $$$O(N \log N)$$$ time. We achieve this by delegating the heavy lifting to a Link-Cut Tree (LCT).
The Core Idea: LCT = Suffix Link Tree
To understand this technique, we must establish one strict rule: The Link-Cut Tree is built exactly on the Suffix Links. If state u has a suffix link to state v (st[u].link = v), we represent this in the LCT by making v the parent of u (lct.link(u, v)). Thus, the path from any node u to the root of the LCT represents the exact chain of its suffix links.
The Bottleneck: The $$$O(N)$$$ Redirection Loop
In a standard SAM, when we add a transition and find a state q that needs to be cloned into clone, we must redirect the transitions of p and its suffix link ancestors to point to the new clone: cpp // The notorious O(N) worst-case loop in a Trie while (p != 0 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; } In a linear string, climbing these links is globally amortized $$$O(N)$$$. But in a Trie, manually redirecting transitions means explicitly traversing paths that can be arbitrarily long and visited multiple times across different branches, causing the $$$O(N^2)$$$ worst-case.
The Magic: Proving We Can DELETE The Redirection Loop!
If you scroll down to the final implementation, you will notice something shocking: The redirection while loop is physically deleted from the code. We never explicitly redirect the ancestors!
How is this mathematically sound? Let's prove why we can completely bypass this step.
1. The "Stale" Transitions
Instead of updating the next transitions of the ancestors, we purposefully do nothing. We let them become "stale." They will continue pointing to the original node they were built with. We will call this original node q_base.
2. The Anatomy of Clones
Over time, as the Trie grows, q_base might be cloned multiple times. Every time we clone a state, the new clone takes the shorter valid lengths, and the old state becomes a child of the clone in the Suffix Link Tree. If q_base is cloned 5 times, q_base will sit at the very bottom of a chain of 5 clones in the Suffix Link Tree.
3. Resolving the "True" State Dynamically
Suppose we are at an ancestor state p representing a length $$$L$$$. We want to transition via character c. The true target state must accommodate the length $$$L + 1$$$.
If we check st[p].next[c], it blindly throws us to the stale q_base. But because q_base is at the bottom of the clone chain, we know for a fact that the true target state is an ancestor of q_base in the Suffix Link Tree.
4. The LCT Range Check
In a SAM, every state represents a continuous range of string lengths: from min_len = link_len + 1 to max_len = len. Since the LCT perfectly represents the Suffix Link Tree, we can simply ask the LCT to resolve the stale transition:
"Start at
q_baseand walk towards the root. Find the unique node whose valid length range[link_len + 1, len]contains $$$L + 1$$$."
Instead of climbing the suffix links one by one ($$$O(N)$$$), the get_node function accesses q_base, pulls the path into a Splay Tree, and uses binary search to find this exact cloned state in $$$O(\log N)$$$ time!
Conclusion: We don't need to manually redirect transitions because the LCT can dynamically resolve any stale transition to its true cloned state on the fly.
Splitting / Cloning a State using LCT
When we clone state q into clone, the structure of the suffix link tree changes. In our LCT, we sever a branch and insert a node in the middle in $$$O(\log N)$$$: 1. lct.cut(q) : Disconnect q from its parent. 2. lct.link(clone, old_link_of_q) : Connect clone to q's old parent. 3. lct.link(q, clone) : Connect q to clone.
Full Implementation
Here is the complete unified C++ implementation, combining the LCT operations, the binary search get_node, and the supercharged extend function into clean structures, this implementation solve problem J in JCPC 2026.
Complexity Analysis
- Time Complexity: $$$O(N \log N)$$$ where $$$N$$$ is the total number of characters added to the Trie. Every
extendcall makes a constant number of LCT operations (access,link,cut,get_node), each taking amortized $$$O(\log N)$$$. - Space Complexity: $$$O(N \cdot \Sigma)$$$ for the SAM transitions + $$$O(N)$$$ for the LCT nodes.
Where to practice?
If you want to test this exact implementation, I originally used this technique to solve a specific problem in JCPC 2026 porblem J.
Since the contest is hosted in Codeforces group, you won't be able to access the problem directly. You will need to join the group first using this link: https://codeforces.me/group/Rilx5irOux/blog
Applications & Conclusion
This setup is incredibly powerful for querying string properties online as the Trie grows. You can maintain prefix sums of occurrences or dynamically query the total number of distinct substrings in the Trie at any point in time without rebuilding.
I hope you found this detailed breakdown useful. Let me know in the comments if you have any questions or variations on this technique!
