Suffix Automaton

A suffix automaton (SAM) of a string S is the minimal deterministic finite automaton (DFA) that accepts exactly the set of all substrings of S. “Minimal” means: among all DFAs that accept this language, it has the fewest states and transitions. For a string of length n, the suffix automaton has at most 2n − 1 states and at most 3n − 4 transitions — strictly linear in n, regardless of alphabet size — and it can be built online in O(n) time for a constant-size alphabet (or O(n log|Σ|) for an arbitrary alphabet) by Blumer et al.’s 1983 algorithm. It is often described as the “best of both worlds” between Suffix Array and Suffix Tree: it has the suffix tree’s per-query power, the suffix array’s compactness on small alphabets, and a beautifully short implementation (~30 lines). The price of admission is a steep conceptual ramp: the construction’s correctness rests on the notion of “endpos-equivalence classes” of substrings, which is genuinely subtle. Once internalized, SAM unlocks elegant linear-time solutions to: counting distinct substrings, longest common substring of two (or many) strings, substring frequency, k-th smallest substring, and the number of occurrences of each distinct substring — all in O(n) construction + O(n) post-processing.

1. Intuition — A Compressed DAG of All Substrings

Imagine you want to build a data structure that, given a string S, can answer “is T a substring of S?” for any query T in O(|T|) time. The simplest answer is to build a Trie of every substring of S: there are O(n²) substrings, so the trie has O(n²) nodes — too big. The Suffix Tree compresses substrings into a tree of O(n) nodes by sharing common prefixes among suffixes. The suffix automaton goes one step further: it shares not only common prefixes but also common occurrence patterns — two distinct substrings that always appear in the same set of positions in S are merged into a single state.

This merging is the key insight. Define, for any substring t of S, the set endpos(t) = {positions where t ends in S}. Two substrings t₁, t₂ with endpos(t₁) = endpos(t₂) are behaviorally indistinguishable with respect to “what comes next in S” — they have the same future. The minimal DFA recognizing the substring language has one state per endpos-equivalence-class of substrings. There are at most 2n − 1 such classes for a length-n string, giving the linear state count.

The real-world analogy: think of a graph of city-routes. Two cities A and B might be different names, but if every route through A is also a route through B and vice versa (they’re on the same set of itineraries), you can merge them into one waypoint without losing any routing information. The suffix automaton is doing exactly this merging on substrings: two substring-names that have the same set of occurrences (= same set of “futures”) become one state.

The construction algorithm is online: it processes characters of S left-to-right and maintains the suffix automaton of the prefix seen so far. After each character is added, the automaton is still minimal and complete for the current prefix. This is what makes it usable for streaming inputs.

2. Tiny Worked Example

Let’s build SAM("aab") step by step. The automaton has, in addition to goto transitions, a suffix link from each state to its parent in the suffix-link tree (which mirrors the suffix-tree structure).

2.1 After processing `""` — initial state

One state: q₀ (the initial / start state, sometimes called t₀). It accepts the empty string and has no transitions.

q₀: [ε], endpos = {0}, suffix_link = none, len = 0

2.2 After processing `"a"`

Add a character a. New state q₁ is created with len = 1, transition q₀ --a--> q₁. Suffix link q₁.link = q₀.

q₀: len=0, endpos⊇{0,1}
q₁: len=1, endpos⊇{1}, link → q₀

Transitions: q₀ --a--> q₁

State q₁ represents the substring(s) ending at position 1 — namely "a".

2.3 After processing `"aa"`

Add a second a. Walk back from the most recent state along suffix links, adding new transitions. Create a new state q₂ with len = 2. Walk: q₁ has no a-transition; add q₁ --a--> q₂. Walk to q₁.link = q₀; q₀ has an a-transition (to q₁). At this point we’d “clone” if q₁’s len were q₀.len + 1 — and it is (1 = 0+1), so we don’t clone. Set q₂.link = q₁.

q₀: len=0
q₁: len=1, link → q₀
q₂: len=2, link → q₁

Transitions: q₀ --a--> q₁
             q₁ --a--> q₂

State q₂ represents the substring "aa" (and, since q₁.endpos would also be {1, 2} now after this step, q₁ represents the substring "a" ending at positions 1 and 2).

2.4 After processing `"aab"`

Add b. Create q₃ with len = 3. Walk back from q₂: no b-transition; add q₂ --b--> q₃. Walk to q₂.link = q₁: no b-transition; add q₁ --b--> q₃. Walk to q₁.link = q₀: no b-transition; add q₀ --b--> q₃. We’ve reached the initial state, so set q₃.link = q₀.

q₀: len=0
q₁: len=1, link → q₀     (represents "a")
q₂: len=2, link → q₁     (represents "aa")
q₃: len=3, link → q₀     (represents "b", "ab", "aab")

Transitions: q₀ --a--> q₁     q₀ --b--> q₃
             q₁ --a--> q₂     q₁ --b--> q₃
             q₂ --b--> q₃

Final SAM for "aab" has 4 states and 5 transitions. The substring set accepted: starting from q₀, follow any path of transitions:

ε (path length 0): just q₀ — accept (q₀ is, by convention, an accepting “empty” state).
a → q₁
aa → q₂
aab → q₃
ab → q₁ -b-> q₃
b → q₃

Six distinct substrings (including empty): {"", "a", "b", "ab", "aa", "aab"}. Indeed "aab" has n(n+1)/2 + 1 = 7 substring positions but only 6 distinct substring strings ("a" appears twice). The SAM enumerates the distinct ones.

The crucial subtlety the worked example doesn’t show: state cloning. When the walk-back encounters an existing transition p --c--> q where q.len > p.len + 1, it must clone q into a new state q' with len = p.len + 1 to maintain the minimality invariant. The general construction handles this; an example showing a clone needs a 5+ character string with repetitions. See cp-algorithms.com for a full clone-triggering walkthrough on "abcbc".

2.5 The suffix-link tree

The suffix links form a tree rooted at q₀ (every state’s link eventually reaches q₀). For "aab":

        q₀
       /  \
      q₁   q₃
       |
      q₂

This tree is isomorphic to the suffix tree of the reversed string "baa". That correspondence is one of the most elegant facts about SAMs: a suffix automaton of S is (up to relabeling) the suffix tree of S^R, traversed differently. The suffix-link tree is the structure most SAM applications work with — it answers occurrence-count and longest-common-substring queries by aggregating data along the tree.

3. Algorithm — Blumer et al.’s Online Construction

The construction maintains, after each character, a state last that represents the longest suffix of the prefix processed so far. Each new character extends last to a new state and may require state cloning to preserve minimality.

3.1 State structure

state := {
    len:  int,                    # length of the longest substring in this state's endpos-class
    link: state,                  # suffix link to the parent in the suffix-link tree
    next: map<char, state>        # outgoing transitions
}

The shortest substring in a state q’s class has length q.link.len + 1; the longest has length q.len. So each state represents a range of substring lengths [q.link.len + 1, q.len], all of which share the same endpos set.

3.2 Pseudocode

SuffixAutomaton(S):
    init := new state(len=0, link=null)
    last := init
    for c in S:
        cur := new state(len = last.len + 1)
        p := last
        # Walk back along suffix links, adding c-transitions to cur until we
        # find a state that already has a c-transition (or hit the root).
        while p is not null and c not in p.next:
            p.next[c] = cur
            p = p.link
        if p is null:
            cur.link = init
        else:
            q := p.next[c]
            if q.len == p.len + 1:
                # No cloning needed — q's substring is a direct extension of p.
                cur.link = q
            else:
                # Clone q into clone with len = p.len + 1, redirecting transitions.
                clone := new state(
                    len = p.len + 1,
                    link = q.link,
                    next = copy of q.next
                )
                # Redirect c-transitions from p (and earlier ancestors) that pointed to q
                # but should now point to clone (because they correspond to shorter strings).
                while p is not null and p.next.get(c) == q:
                    p.next[c] = clone
                    p = p.link
                q.link = clone
                cur.link = clone
        last = cur
    return init   # the entire automaton is reachable from init

The two paths through the algorithm:

No-clone case (q.len == p.len + 1): the existing state q represents exactly the substring p’s longest substring + character c. We can directly link the new state’s suffix link to q.
Clone case (q.len > p.len + 1): q represents multiple substrings (a length range). Some of them are just p + c (shorter); some are longer extensions present in earlier prefixes. We need to split q into:
- clone (length range [q.link.len + 1, p.len + 1]) — the shorter substrings that ended where cur’s longest does;
- q (now with q.link = clone, length range [clone.len + 1, q.len]) — the longer substrings that have a different (subset) endpos.

This is the part most students struggle with. The intuition: cloning preserves the invariant that each state’s endpos-class contains exactly the strings whose endpos sets coincide. After adding a new occurrence (the new c), some strings that previously shared an endpos with q now have a strictly larger endpos, while others (the shorter ones) acquired a new endpos. Splitting q separates those two cases.

4. Python Implementation

A complete suffix automaton in Python, with applications to distinct-substring counting and longest-common-substring extraction:

from dataclasses import dataclass, field
 
@dataclass
class SAMState:
    length: int = 0
    link: int = -1                 # index into the SAM's state list; -1 means no link (root only)
    next: dict[str, int] = field(default_factory=dict)
    cnt: int = 0                   # occurrence count, computed in post-processing
 
class SuffixAutomaton:
    def __init__(self) -> None:
        self.states: list[SAMState] = [SAMState(length=0, link=-1)]
        self.last: int = 0          # index of the state representing the current full prefix
 
    def extend(self, c: str) -> None:
        """Append character `c` to the string represented by this SAM."""
        cur = len(self.states)
        self.states.append(SAMState(length=self.states[self.last].length + 1, cnt=1))
        p = self.last
        # Walk up suffix links, adding c-transitions to cur.
        while p != -1 and c not in self.states[p].next:
            self.states[p].next[c] = cur
            p = self.states[p].link
        if p == -1:
            self.states[cur].link = 0
        else:
            q = self.states[p].next[c]
            if self.states[q].length == self.states[p].length + 1:
                self.states[cur].link = q
            else:
                # Clone state q.
                clone = len(self.states)
                self.states.append(SAMState(
                    length=self.states[p].length + 1,
                    link=self.states[q].link,
                    next=dict(self.states[q].next),
                    cnt=0,                 # clones start with 0 occurrences
                ))
                while p != -1 and self.states[p].next.get(c) == q:
                    self.states[p].next[c] = clone
                    p = self.states[p].link
                self.states[q].link = clone
                self.states[cur].link = clone
        self.last = cur
 
    def build(self, s: str) -> None:
        for ch in s:
            self.extend(ch)
 
    def count_distinct_substrings(self) -> int:
        """Total number of distinct non-empty substrings of the string."""
        # Each state q (except the root) contributes q.length - q.link.length distinct substrings.
        total = 0
        for i in range(1, len(self.states)):
            total += self.states[i].length - self.states[self.states[i].link].length
        return total
 
    def occurrence_counts(self) -> list[int]:
        """Compute, for each state, the size of its endpos set (= number of occurrences
        of any substring represented by that state).
 
        Done by topological-sort propagation along suffix links: a state's endpos count
        is the sum of its children's endpos counts in the suffix-link tree, plus its own
        (1 if the state was created as a 'cur' during extension, 0 if it was a clone)."""
        n = len(self.states)
        # Sort by length descending — guarantees children processed before parents.
        order = sorted(range(n), key=lambda i: -self.states[i].length)
        for i in order:
            link = self.states[i].link
            if link != -1:
                self.states[link].cnt += self.states[i].cnt
        return [s.cnt for s in self.states]
 
 
# Worked example from §2:
sam = SuffixAutomaton()
sam.build("aab")
assert len(sam.states) == 4
assert sam.count_distinct_substrings() == 5    # "a", "aa", "aab", "ab", "b" — five non-empty distinct substrings
 
# Distinct-substring count for a longer example:
sam2 = SuffixAutomaton()
sam2.build("abcbc")
# Substrings: a, ab, abc, abcb, abcbc, b, bc, bcb, bcbc, c, cb, cbc — 12 distinct
assert sam2.count_distinct_substrings() == 12

The occurrence_counts method illustrates the “post-processing on the suffix-link tree” pattern. Most SAM applications boil down to “propagate some quantity along the suffix-link tree in topological (length-descending) order.” This is analogous to how Suffix Tree applications often boil down to walking the tree.

5. Complexity

5.1 Number of states and transitions

For a string of length n:

States: at most 2n − 1, for n ≥ 2 (Blumer et al. 1983 proved this; the bound is tight). The extremal string is a·b^(n−1) — i.e. "abbb…b" — which forces the maximum state count (cp-algorithms; Wikipedia: Suffix automaton).
Transitions: at most 3n − 4, for n ≥ 3 (also tight). The extremal string is a·b^(n−2)·c — i.e. "abb…bc", the maximum-state string with a distinct trailing character — which forces the maximum transition count (cp-algorithms; Wikipedia: Suffix automaton).

Both bounds are independent of alphabet size. The constants come from the structure of endpos-equivalence classes. Note that the state-extremal string ab^(n−1) and the transition-extremal string ab^(n−2)c are different: the trailing distinct c is what pushes the transition count from below 3n − 4 up to the bound, while a string of the ab^(n−1) form maximizes states but not transitions. The two bounds are achieved by separate families, a detail many summaries get wrong by attributing the 3n − 4 transition bound to the all-b string.

5.2 Construction time

The canonical statement (Wikipedia, cp-algorithms): the automaton is built in O(n) time when the alphabet size |Σ| is treated as a constant; for an arbitrary alphabet it is O(n · log|Σ|) time with O(n) space when transitions are stored in balanced binary trees, or O(n) time with O(n · |Σ|) space when each state stores a direct-indexed transition array.
With next stored as a hash map, lookups/inserts are amortized O(1) in expectation, giving O(n) expected construction time independent of |Σ|.
The suffix-link walk in extend is bounded amortized: a state’s suffix link only ever goes to a strictly shorter-length state, and the total number of state visits across all walk-backs over the entire construction is O(n) by a potential argument on the length of the longest suffix represented by last. So the number of state visits is linear; the only super-linear factor that can appear is the per-transition lookup cost, which is O(log|Σ|) for balanced trees and O(1) expected for hashing.

For interview / contest, “O(n) construction (alphabet constant), or O(n log|Σ|) for arbitrary alphabets” is the right one-liner.

5.3 Space

States: O(n).
Transitions: O(n) per state via next dictionaries; total O(n) for the whole automaton (since transitions sum to O(n) — see §5.1).
Each state stores len, link, and (worst case) O(|Σ|) transitions.

Total space: O(n · |Σ|) with dense arrays, O(n) expected with hashed transitions.

5.4 Why the state count is linear

The “at most 2n − 1 states” bound is non-obvious. Proof sketch (full proof in Blumer et al. 1983):

Every state q ≠ q₀ corresponds to a nonempty endpos-equivalence class of substrings.
For each pair of substrings in the same class, their endpos sets are equal; for any two strings in different classes, their endpos sets are different.
Consider the suffix-link tree. Its nodes are the SAM states. Its leaves correspond to the prefix-extensions added at each extend call (one leaf per character); some non-leaf nodes are clones. There are at most n leaves and at most n − 1 internal nodes (clones), totaling 2n − 1.

This is exactly analogous to the linear-size bound of suffix trees: there are n leaves (one per suffix) and at most n − 1 internal branching nodes.

6. Variants and Use Cases

6.1 Distinct substring count — O(n)

After construction, sum state.length − state.link.length across all non-root states (§4 implementation). Each state represents length − link.length distinct substrings (one per length in its range), and these are pairwise disjoint across states.

6.2 Longest common substring of two strings — O(n + m)

Build SAM of S (length n). Walk through T (length m) maintaining a current state v and a current length l:

For each character c of T:
- If c in v.next: extend by following the transition, l += 1.
- Otherwise: walk back along suffix links of v until finding a state with a c-transition (or reach q₀); then update v and l accordingly.
Track the maximum l seen. That’s the length of the longest common substring; the substring itself is the corresponding prefix of T.

The walk-back is amortized O(1) per character of T by the same potential argument as KMP. Total: O(n + m).

6.3 Substring frequency — O(n) post-processing

Each substring’s number of occurrences in S equals the size of its state’s endpos set, which equals the size of the subtree under that state in the suffix-link tree. Compute via topological-sort propagation (§4 occurrence_counts).

6.4 k-th smallest distinct substring — O(n) preprocessing + O(answer length) per query

Treat the SAM as a DAG where each path from q₀ is a distinct substring. Count, for each state, the number of distinct substrings reachable from it (via DP on the DAG). To find the k-th smallest substring: descend from q₀ choosing the lexicographically smallest transition whose subtree size is ≥ remaining k, decrementing as you go.

6.5 Multiple-string longest common substring

For k strings: build SAM of one (the shortest), then for each other string, walk through it with the SAM and record, at each state, the maximum match length found. Combine across all strings (take the minimum per state, then maximize). O(total length × k).

6.6 Comparison with Suffix Tree and Suffix Array

Aspect	Suffix Tree	Suffix Array (+ LCP)	Suffix Automaton
Construction	O(n) (Ukkonen)	O(n) (SA-IS) or O(n log n) (doubling)	O(n) (Blumer et al.)
State count	n leaves + O(n) internal	n integers + O(n) for LCP	≤ 2n - 1 states
Memory (typical)	~20·n bytes	~8·n bytes	~10·n bytes (dict per state)
Online	Yes (Ukkonen)	No	Yes
Substring search	O(\|P\|)	O(\|P\| + log n)	O(\|P\|)
Distinct substrings	O(n)	O(n)	O(n)
Longest common substring (2 strings)	O(n+m)	O(n+m)	O(n+m)
Implementation lines	100+	30 + 20 (LCP)	30

Why prefer SAM: shortest correct implementation among the three; online; clean semantics for substring-occurrence-frequency queries. Why not: the cloning logic is hard to debug; suffix array is often “good enough” with simpler code; for read-only static text, suffix array’s smaller memory wins.

7. Pitfalls

7.1 Mishandling the clone case

The if q.len == p.len + 1 branch is the most error-prone part of every SAM implementation. Subtle wrong-answer bugs come from:

Not redirecting all ancestor transitions that point to q (must walk up suffix links until the chain breaks).
Cloning next by reference instead of by copy — then mutations to q.next poison clone.next.
Forgetting to set clone.link = q.link before updating q.link = clone (would create a cycle).

Always test against "abcbc" or "aabbaabb" — both trigger cloning multiple times.

7.2 Off-by-one in length attribution

The length range [link.len + 1, len] is inclusive on both ends. Computing len - link.len + 1 is wrong; it should be len - link.len to count the number of distinct substring lengths in the class.

7.3 Empty input

SuffixAutomaton().count_distinct_substrings() on an empty SAM (only the root) should return 0. Implementations that compute len(states) - 1 get this right; ones that hardcode loop ranges may not.

7.4 Forgetting that clones don’t contribute to endpos counts

In the occurrence-count post-processing (§4), clones are created with cnt = 0 because they don’t represent a “new occurrence” — they just split an existing state’s class. cur states (the ones created in extend before any cloning) get cnt = 1. Mixing these up gives wildly wrong frequency counts.

7.5 Using SAM when Suffix Array suffices

For one-shot “find longest common substring of two strings” without a streaming requirement, SA + LCP is shorter to write (~50 lines vs ~30 lines) and equally fast. SAM’s win is online + frequency queries + DAG-of-substrings semantics. If you’re not using those, you may be over-engineering.

7.6 Confusion between “suffix automaton” and “factor automaton”

Some references use “factor automaton” or “directed acyclic word graph (DAWG)” interchangeably with suffix automaton. They are the same object up to whether the accepting states are explicitly marked. A “DAWG” historically refers to the same structure but emphasizes the graph view over the automaton view. Modern usage treats them as synonyms.

7.7 Alphabet-size bias

SAM is alphabet-agnostic in state count but the per-character transitions cost O(|Σ|) for dense storage or O(1) hashed. For DNA (|Σ| = 4) dense arrays are fast; for arbitrary Unicode, hashed transitions are a must. Conflating the two costs leads to misquoted complexities.

8. Diagram — SAM Structure for `"abcbc"`

The structure below was produced by running the §4 implementation on "abcbc" and reading off every state’s len, link, and transition map — it is the actual automaton, not a hand-sketch. Positions are 0-indexed (a@0, b@1, c@2, b@3, c@4); endpos sets list the 0-indexed positions where a substring ends.

graph TD
    q0(("q0: ε &nbsp; len=0"))
    q1(("q1: a &nbsp; len=1"))
    q2(("q2: ab &nbsp; len=2"))
    q3(("q3: abc &nbsp; len=3"))
    q4(("q4: cb,bcb,abcb &nbsp; len=4"))
    q6(("q6: abcbc &nbsp; len=5"))
    qB(("qB: b &nbsp; len=1"))
    qBC(("qBC: c,bc &nbsp; len=2"))

    q0 -- a --> q1
    q1 -- b --> q2
    q2 -- c --> q3
    q3 -- b --> q4
    q4 -- c --> q6
    q0 -- b --> qB
    qB -- c --> qBC
    qBC -- b --> q4
    q0 -- c --> qBC

    q1 -.link.-> q0
    q2 -.link.-> qB
    q3 -.link.-> qBC
    q4 -.link.-> qB
    q6 -.link.-> qBC
    qB -.link.-> q0
    qBC -.link.-> q0

What this diagram shows. The suffix automaton of "abcbc" — 8 states (matching the actual construction). Solid arrows are next transitions labelled by character; dashed arrows are suffix_links. Each state’s label lists the substrings in its endpos-class and its longest length len. The key things to read off it:

Merged states are the whole point. c (ends at {2,4}) and bc (ends at {2,4}) have identical endpos sets, so they collapse into a single state qBC — there is no separate “qc” node. This merging is exactly why a SAM is smaller than a trie of substrings, and it is what an earlier draft of this note got wrong by drawing c and bc as separate states.
The “spine” q0 → q1 → q2 → q3 → q4 → q6 spells the full input; q6 represents the whole string "abcbc" (endpos {4}).
The off-spine states qB (b, endpos {1,3}) and qBC (c/bc, endpos {2,4}) hold the substrings that recur at multiple positions — note both q0 -b-> qB and q0 -c-> qBC start fresh branches, and qBC -b-> q4 rejoins the spine because cb/bcb/abcb all end at the same place.
The suffix-link tree (dashed arrows, read child→parent) is rooted at q0 with children {q1, qB, qBC}, then qB’s children {q2, q4} and qBC’s children {q3, q6}. Propagating endpos counts leaf-to-root over this tree answers occurrence-frequency queries in O(n).
State count is 8, below the 2n − 1 = 9 ceiling for n = 5. abcbc does not saturate the bound — the extremal ab^(n-1) family (see §5.1) does. The 8 states break down as: 1 initial + 5 “cur” states (one created per character of the input) + 2 clones (verified by instrumenting the §4 code: adding the second b and the second c each fire the clone branch, because the existing target state’s len exceeds p.len + 1). So this example does exercise the cloning logic — qB and qBC are precisely the clones, which is why their len values sit below their out-transitions’ targets.

The bidirectional structure (forward DAG + backward tree) is what makes SAM such a powerful query engine: both views answer different questions, and they’re maintained automatically by the same construction.

9. Common Interview Problems

LC# / Source	Problem	Use of SAM
LC 1044	Longest Duplicate Substring	SA + LCP is the textbook answer; SAM solves it via “longest substring with endpos count ≥ 2.”
LC 1923	Longest Common Subpath (k strings)	Multi-string LCS via SAM is one of the cleanest approaches.
LC 1062	Longest Repeating Substring	Same as LC 1044 — SAM finds longest substring with cnt ≥ 2 in O(n).
LC 1392	Longest Happy Prefix	KMP is the textbook answer; SAM also solves it (via length of longest substring that is both a prefix and suffix).
Codeforces 235C	Cyclical Quest	Build SAM of `s`; for each query, find longest match — O(n + Σ
Codeforces 873F	Forbidden Indices	Substring freq + DP on SAM.
ICPC / SPOJ SUBLEX	Lexicographically k-th substring	DAG DP on SAM (§6.4).
AtCoder ABC 213H	Closed Walk	Generating-function-on-SAM technique; advanced.

The pattern: anything that involves “all substrings of S” + a quantitative property (count, length, lexicographic rank, frequency) is a candidate for SAM.

10. Open Questions

Why exactly does cloning preserve the minimality invariant? The cp-algorithms.com proof is operational; a clean information-theoretic explanation would be illuminating.
Is there a known parallel construction of SAM? The dependencies between consecutive extend calls seem fundamental, but the suffix-link tree might be amenable to bulk operations.
How does SAM compare to factor oracles (Allauzen-Crochemore-Raffinot 1999) — strictly smaller, accepts a superset of substrings? For some applications the oracle’s slight imprecision is acceptable in exchange for ~2× space savings.

Both bounds were verified against cp-algorithms and Wikipedia: Suffix automaton, which both attribute them to Blumer et al.’s original 1983 work. The state bound 2n − 1 holds for n ≥ 2 and is achieved by ab^(n−1); the transition bound 3n − 4 holds for n ≥ 3 and is achieved by the distinct-trailing-character string ab^(n−2)c (see §5.1). A common error — including in an earlier draft of this note — is to claim the all-b string aaa…a or abbb…b achieves the transition bound; it does not. The state-extremal and transition-extremal families are genuinely different (§5.1).

11. See Also

Suffix Tree — closely related; SAM(S) ≡ suffix tree of S^R structurally
Suffix Array — alternative compact substring index
Knuth-Morris-Pratt — single-pattern matching primitive
Aho-Corasick — multi-pattern alternative for fixed dictionary
Trie — degenerate ancestor (one state per prefix, not per equivalence class)
Z-Algorithm
Rabin-Karp
String Hashing
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Suffix Automaton

Suffix Automaton

1. Intuition — A Compressed DAG of All Substrings

2. Tiny Worked Example

2.1 After processing "" — initial state

2.2 After processing "a"

2.3 After processing "aa"

2.4 After processing "aab"

2.5 The suffix-link tree

3. Algorithm — Blumer et al.’s Online Construction

3.1 State structure

3.2 Pseudocode

4. Python Implementation

5. Complexity

5.1 Number of states and transitions

5.2 Construction time

5.3 Space

5.4 Why the state count is linear

6. Variants and Use Cases

6.1 Distinct substring count — O(n)

6.2 Longest common substring of two strings — O(n + m)

6.3 Substring frequency — O(n) post-processing

6.4 k-th smallest distinct substring — O(n) preprocessing + O(answer length) per query

6.5 Multiple-string longest common substring

6.6 Comparison with Suffix Tree and Suffix Array

7. Pitfalls

7.1 Mishandling the clone case

7.2 Off-by-one in length attribution

7.3 Empty input

7.4 Forgetting that clones don’t contribute to endpos counts

7.5 Using SAM when Suffix Array suffices

7.6 Confusion between “suffix automaton” and “factor automaton”

7.7 Alphabet-size bias

8. Diagram — SAM Structure for "abcbc"

9. Common Interview Problems

10. Open Questions

11. See Also

Graph View

Table of Contents

Backlinks

2.1 After processing `""` — initial state

2.2 After processing `"a"`

2.3 After processing `"aa"`

2.4 After processing `"aab"`

8. Diagram — SAM Structure for `"abcbc"`