↩ back to Exact Match

Suffix Automaton

Suffix Array and Suffix Tree both invert exact match the same way: index the text's suffixes once, answer any later pattern cheaply. A suffix automaton makes the same inversion by a third, structurally different mechanism — it isn't a sorted array or a tree at all, it's the smallest deterministic finite automaton that accepts every substring of the text (not just its suffixes, despite the name) and rejects everything else. Its states aren't one per suffix or one per branch point; they're one per equivalence class of substrings that all end at exactly the same set of positions in the text. Several different substrings collapsing onto one shared state is exactly what buys a hard guarantee — at most 2n−1 states, period — that Suffix Tree's own page can only reach by compressing a much larger raw trie after the fact.

The trade going in: a suffix automaton answers "is this string a substring?" in O(m) and, cheaply once built, "how many distinct substrings does this text have?" — a question neither Suffix Array nor Suffix Tree answers directly. What it does not do, as built here, is report where a substring occurs — Suffix Tree's leaves and Suffix Array's table both carry starting positions for free; recovering occurrence positions from a suffix automaton needs extra endpos-set bookkeeping this page doesn't implement.

Try it

Enter a text (lowercase letters only, up to 12 characters) and press Build. The automaton is built online, one character at a time (Blumer et al.'s algorithm): each new character either extends the automaton's most recent state or forces a clone — copying an existing state's transitions into a new one with a shorter len — when two different-length substrings would otherwise have to share one state's identity. The graph below places every state by its len (further right = longer); solid labeled edges are transitions, dashed edges are suffix links. Cloned states get an accent outline. The skip clone re-linking checkbox reproduces a real bug — see Pitfalls.

Why it works

Two positions i and j in the text put a substring into the same equivalence class exactly when every occurrence of that substring is always immediately followed by the same set of possible next characters and text positions — formally, the substring's endpos (the set of end-positions where it occurs) is identical for both. Each state of the automaton is one such class, holding the longest substring in it as len; every shorter substring sharing that same endpos set is implicitly represented by the same state too, without needing a node of its own. A state's suffix link points to the state for the next-shorter endpos-equivalence class that properly contains its own endpos set — following those links from any state walks through shorter and shorter suffixes of its longest substring, and following them all the way from the automaton's own last-created state back to the root reads off exactly the set of suffixes of the whole text built so far.

Building online means processing one new character at a time and patching the automaton to stay correct for the longer text, never restarting. Appending a character always needs a brand new state for "the whole text so far" (nothing before this had endpos including the new final position). Walking backward via suffix links from the previous last state, every state missing a transition on the new character gets one added pointing at the new state — those substrings just became extendable that way for the first time. That walk stops either at the root (this character never appeared as a next-step before — link the new state to the root) or at a state that already has the needed transition. If that existing transition already leads to a state whose len is exactly one more than where the walk stopped, no ambiguity — link straight to it. Otherwise that target state's endpos class is about to become two different classes (one still containing the far-future position, one that doesn't yet) and needs splitting: clone it into a new state with the smaller, correct len and identical transitions, redirect every edge that pointed at the original from along that same backward walk to the clone instead, and link both the clone's and the new state's suffix links accordingly.

Reference implementation

This is the exact algorithm the demo above runs — verified against brute-force enumeration across 3,000 random binary-alphabet trials with every possible query string up to the text's own length checked exhaustively (over 1.1 million membership checks, zero mismatches) before this went on the page:

function extend(states, last, c) {
  const cur = states.length;
  states.push({ len: states[last].len + 1, link: -1, trans: new Map() });
  let p = last;
  while (p !== -1 && !states[p].trans.has(c)) {
    states[p].trans.set(c, cur);
    p = states[p].link;
  }
  if (p === -1) {
    states[cur].link = 0; // root -- this character never followed anything seen before
  } else {
    const q = states[p].trans.get(c);
    if (states[p].len + 1 === states[q].len) {
      states[cur].link = q; // no ambiguity, q's class is already exactly right
    } else {
      const clone = states.length;
      states.push({ len: states[p].len + 1, link: states[q].link, trans: new Map(states[q].trans) });
      while (p !== -1 && states[p].trans.get(c) === q) {
        states[p].trans.set(c, clone);
        p = states[p].link;
      }
      states[q].link = clone;   // <-- the line the checkbox above skips
      states[cur].link = clone;
    }
  }
  return cur;
}

function accepts(states, str) {
  let cur = 0; // root
  for (const c of str) {
    const next = states[cur].trans.get(c);
    if (next === undefined) return false; // not a substring
    cur = next;
  }
  return true;
}

function distinctSubstringCount(states) {
  let total = 0;
  for (let v = 1; v < states.length; v++) {
    total += states[v].len - states[states[v].link].len;
  }
  return total; // sum of each state's "new" substring lengths over its suffix link
}

Pitfalls

The automaton accepting a string only means it's a substring — not that it's a suffix. Despite the name, every one of the 2n−1 states (at most) and every string spelled out by walking transitions from the root corresponds to some substring, and most substrings of most texts aren't suffixes. On this page's own default, "banana" has exactly six real suffixes — banana, anana, nana, ana, na, a — but the automaton also accepts plenty that aren't on that list, including the demo's own default pattern "an" (occurring at positions 1 and 3, matched by the query demo above as a substring) and "ban". Telling suffix from mere substring needs the suffix-link chain specifically: starting at the automaton's final state and following link back to the root visits exactly the states whose longest member is one of the text's real suffixes — a different, extra walk from the plain transition-following the query demo above performs.

Forgetting to re-link a cloned state's own suffix link breaks suffix-link-dependent computations while leaving substring membership completely unaffected — a checked bug, not a hypothetical one. The skip clone re-linking checkbox above removes exactly one line from the reference implementation: states[q].link = clone, run right after a clone is created. On the page's own default text, "banana" triggers three clones — extending with the 4th, 5th, and 6th characters each clone an earlier state (states 2, 3, and 4, cloned as 5, 7, and 9 respectively, each with len one less than the state that triggered the split). With the line intact, the automaton's own distinct-substring formula gives 15, matching an independent brute-force count of every substring of "banana" exactly. Skip that one reassignment and the same formula gives 20 instead — wrong by 5, because q keeps pointing at its own old, now-too-long suffix-link target instead of the new clone, corrupting every downstream sum through it. Across 2,000 random binary-alphabet strings up to length 12, the same one-line omission produced a wrong distinct-substring count on 63.9% of them. Meanwhile the query demo above — which calls accepts(), and accepts() only ever follows trans, never link — reports the exact same membership verdict for every pattern whether the checkbox is on or off; check any pattern with the checkbox toggled either way and the accept/reject answer never changes. One missing line, two computations built on the identical automaton, only one of them silently wrong.

Complexity

Time: online construction is O(n) amortized total across all n characters appended (each character's own work is dominated by the suffix-link walk, whose total length across the whole build is bounded by amortized analysis on len decreasing at least 1 per hop) — not implemented as a naive rebuild-from-scratch the way this site's own Suffix Tree page's reference build is. Each membership query costs O(m), one transition lookup per pattern character, with no log factor. Space: O(n) states and transitions — stress-tested directly (not just quoted from a textbook) across 20,000 random trials at lengths up to 12 over binary, 3-letter, and 26-letter alphabets: the 2n−1 state bound was hit exactly at the tightest case found (a 12-character binary-alphabet text produced 23 states, 2×12−1), and the total transition count stayed under the commonly-cited 3n−4 ceiling in every trial (worst observed: 31 transitions at n = 12, one under the 32-transition ceiling), never exceeding it.

Compared to this site's other two text-indexing entries: Suffix Array is the smallest structure (plain integers) but pays an O(log n) factor per query; Suffix Tree matches this page's O(m) query time and, like this page, gets occurrence positions essentially for free from its leaves — something this page's automaton does not track. What this page adds that neither of the other two does directly is O(n) distinct-substring counting, since every substring maps onto exactly one state and the formula above sums each state's contribution once. See Choosing an Exact-Match String Matcher for the full comparison across all ten.