How to Learn Suffix Automata: End-Position States, Suffix Links, Cloning and Linear-Time String Indexing

Wait, What?

A structure with only O(n) states can represent every substring of a string—even though a string can have O(n²) distinct substrings.

That compression is the first idea to understand before touching the construction algorithm. A suffix automaton is a compact deterministic finite automaton that captures the substring structure of a text. It is not a suffix array, not a suffix tree, not Aho–Corasick, and not a trie with a clever name. Those structures connect, but they own different jobs.

This article owns the suffix-automaton lane: how to learn its state meaning, suffix links, cloning and linear online construction, then use those ideas for professional string indexing.

Quick Read

Beginner: think in paths spelling substrings.
Intermediate: understand each state’s maximum length and suffix link.
Advanced: learn why cloning is necessary during online extension.
Professional: derive queries, propagate occurrence counts, reason about alphabet representation, memory layout and proof obligations.

The One-Sentence Answer

A suffix automaton groups substrings that have the same future behaviour into states, producing a minimal deterministic automaton for the suffix language and, as a consequence, a compact representation of all substrings of the text.

1. Begin With Substrings, Not Construction Code

Take a short string such as ababa. List a few substrings: a, ab, ba, aba, bab, ababa. Now imagine an automaton whose paths from the start state spell all of them. The surprise is that many prefixes of these paths can share states because their possible continuations are equivalent.

Before coding, ask the learner to predict whether a candidate string is a substring and trace the path that would certify it. This predict–trace–explain routine is deliberately educational: recent programming-education research on self-explanation, worked examples and code tracing suggests that learners benefit when they must retrieve or explain the next state transition rather than merely read finished code.

2. What a State Actually Means

A state does not stand for one substring. It represents an equivalence class of substrings with the same set of ending positions in the original text—the classic endpos view. Practically, each state stores a value often called len: the maximum length of a substring represented by that state.

The state also has transitions by characters and usually a suffix link. The suffix link points toward the state representing the largest proper suffix class that remains relevant when the current context can no longer continue.

3. The Suffix Link Is a Semantic Fallback

Do not teach suffix links as “another pointer”. Ask what information must survive when a longer context fails. The link moves from a more specific equivalence class to the best shorter suffix class that preserves the automaton’s language structure.

For each state v, the shortest substring length represented by that state is len(link(v)) + 1, while the longest is len(v). That interval becomes extremely useful later when counting distinct substrings.

4. Online Construction: Add One Character at a Time

The standard construction processes the text from left to right. Maintain a state called last representing the entire processed prefix. When a new character c arrives, create a new state cur with a larger maximum length, then walk suffix links backwards adding missing transitions labelled c.

extend(c):
    create cur
    len[cur] = len[last] + 1
    p = last
    while p exists and transition(p,c) missing:
        transition(p,c) = cur
        p = link[p]
    ... resolve suffix link of cur ...

At this point many learners think the algorithm is nearly finished. It is not. The difficult case is when an existing transition leads to a state whose length relationship is too large to preserve the minimal-state structure.

5. Why Cloning Exists

Suppose the backward walk reaches a state p that already has a transition on c to state q. If len[p] + 1 == len[q], the structure fits and q can be the suffix-link target. Otherwise, q currently represents contexts that must now be separated.

Create a clone of q: copy its transitions and suffix link, but shorten its maximum length to len[p] + 1. Redirect appropriate transitions that previously pointed to q so they point to the clone, then make both q and the new state link to the clone.

The pedagogical key is to describe the semantic repair before the pointer edits: cloning splits one state’s equivalence role into two roles while preserving accepted paths. If the learner memorises the redirections without understanding that separation, the construction will be fragile.

6. The Three Extension Cases

No prior transition survives: the new state links to the initial state.
Existing transition has the right length: link the new state directly to its destination.
Existing transition is too long: clone the destination and redirect the necessary transitions.

A useful learning exercise is a Parsons-style reconstruction: give the learner these three cases out of order and ask them to place them into the extension logic, then explain the condition that distinguishes each case.

7. Why the Structure Remains Linear in Size

Each processed character creates one ordinary state and may create at most one clone. Therefore a suffix automaton for a non-empty string of length n has at most 2n − 1 states. This is one of the structure’s defining compression results.

With a constant-size alphabet and constant-time transition access, construction is linear. With map-based transitions over larger alphabets, the complexity depends on the transition representation, commonly adding logarithmic factors.

8. First Application: Substring Membership

After building the automaton for text T, test whether pattern P is a substring by starting at the initial state and following transitions for every character of P. If a transition is missing, the pattern is absent. If the entire pattern is consumed, it occurs.

This query looks easy because the difficult work was moved into construction. That is an important algorithmic design lesson: preprocessing can transform many later queries into simple traversals.

9. Count Distinct Substrings

Every non-initial state contributes a number of distinct substrings equal to:

len[v] - len[link[v]]

Summing this quantity over states counts the distinct substrings. This formula is worth deriving, not memorising: a state represents all substring lengths from one more than its suffix-link state’s maximum through its own maximum length.

10. Count Occurrences Correctly

Occurrence counting needs extra information. Mark each ordinary state created during extension with an initial contribution, then propagate counts from longer states toward shorter suffix-link ancestors in decreasing order of len. Clone states normally begin with zero direct occurrence contribution. After propagation, a state’s accumulated count corresponds to the size of its end-position set.

The ordering requirement matters: if counts move before descendants are complete, information is lost. This is a good place to connect to the existing topological and counting ideas without stealing their canonical jobs.

11. Longest Common Substring

Build the suffix automaton for one string. Scan the second string while tracking the current state and current matched length. When a transition fails, follow suffix links until a valid continuation becomes possible, adjusting the matched length. The maximum reached value is the longest common substring length.

Professional understanding means being able to explain why suffix links make this fallback safe, not merely copying the code.

12. Suffix Automaton vs Nearby Structures

Suffix array: sorted suffix positions; excellent for binary-search-based indexing and compact static processing.
LCP array: captures common-prefix information between neighbouring sorted suffixes.
Aho–Corasick: builds an automaton from many patterns and scans a text.
Suffix automaton: builds from one text and compactly represents its substring language.
Suffix tree: compressed trie of suffixes with different structural and implementation trade-offs.

The existence of those articles is why this one stays narrow. It does not re-teach generic string matching or suffix arrays.

13. Common Failure States

Thinking one state equals one substring.
Confusing a suffix link with a parent edge in a tree.
Copying clone transitions but forgetting to adjust clone length.
Redirecting too many or too few transitions to the clone.
Counting clones as direct new occurrences.
Claiming O(n) construction without stating the transition representation and alphabet assumptions.
Using terminal-state language without distinguishing suffix acceptance from general substring paths.

14. Learning Hall Practice Ladder

Level 1: trace substring membership on a completed automaton.
Level 2: label each state with its len and suffix link.
Level 3: predict which suffix links are followed when adding one character.
Level 4: identify an extension that requires cloning and explain why.
Level 5: build the automaton for a five-character string by hand.
Level 6: derive the distinct-substring formula.
Level 7: propagate occurrence counts in length order.
Level 8: compare array, hash-map and ordered-map transitions for a real alphabet.

15. Professional Engineering Questions

How large is the alphabet?
Is the text static or arriving online?
Which queries dominate: membership, counts, longest matches, lexicographic enumeration?
Does pointer-heavy transition storage destroy cache locality?
Would a suffix array or FM-index be smaller or easier to maintain for the workload?
Are Unicode code points, bytes or grapheme clusters the actual symbols?
How will the implementation be fuzz-tested against brute force on small strings?

16. Authoritative Reading

Algorithms for Competitive Programming — Suffix Automaton, updated May 24, 2026, with construction, proofs and applications.
The classical linear-size and linear-construction results trace to work by Blumer, Crochemore and collaborators in the 1980s; modern treatments often present the same core automaton through end-position equivalence.

Final Check

You understand a suffix automaton when you can explain what a state represents, trace suffix-link fallback, justify when cloning is required, derive at least one query from the state-length intervals, and state the assumptions under which the structure is linear in time and space.

Small Group Tutorials