Introduction

Imagine you need to answer the question "does this pattern appear anywhere in this text?" — thousands of times, for thousands of different patterns, all against the same long text. A naive search re-scans the text from scratch every time. A smarter idea: preprocess the text once into an index that answers each query instantly.

The suffix automaton (also called a DAWG — Directed Acyclic Word Graph) is the most elegant such index known. It is a finite-state machine — a compact directed graph — with one extraordinary property: a path through it spells out a string if and only if that string is a substring of the original text. Feed it any candidate pattern; if the automaton accepts it, the pattern is there.

What makes it remarkable is not what it does but how small it is. For a string of length nn, the suffix automaton has at most 2n−12n - 1 states and at most 3n−43n - 4 transitions — proven limits, impossible to beat. And yet it is built in O(n)O(n) time and space by a simple online algorithm: extend the automaton one character at a time, never looking back. Proved and published by Anatolii Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler, and Ross McConnell in 1985.

The suffix automaton sits in the heart of modern text processing — DNA search, plagiarism detection, data compression — and it connects deeply to the related concepts of pattern matching and sequence alignment.

Try It

Type any short string below and press Build. The demo constructs the suffix automaton state by state, then counts every distinct non-empty substring by summing, for each state, the difference between the longest and shortest strings it recognises.

<p class="hint">Type a short string (up to 15 chars) and press <b>Build</b>. The automaton is constructed character by character; then a single linear pass counts every distinct non-empty substring — no brute force needed.</p>
<div class="controls">
  <input id="inp" type="text" maxlength="15" value="abcbc" spellcheck="false" autocomplete="off" />
  <button id="build" type="button">Build</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div id="stats" class="stats"></div>
<div id="vis" class="vis"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .8rem; }
input { font: 600 15px ui-monospace, monospace; padding: .4rem .7rem;
        border: 1.5px solid #adb1b8; border-radius: 8px; width: 11rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .95rem; min-height: 1.4em; margin-bottom: .5rem; }
.stats b { color: #1d3557; }
.vis { overflow-x: auto; padding-bottom: .4rem; }
svg.aut { display: block; }
.log { font-size: .82rem; color: #555; margin-top: .6rem; line-height: 1.6;
       max-height: 90px; overflow-y: auto; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Suffix Automaton (DAWG) – online construction in O(n) time.
// Each state stores:
//   len   – length of the longest string in its endpos class
//   link  – suffix link (parent in the suffix link tree)
//   next  – transition map { char -> state_id }
// After building, distinct substrings = sum over states (excluding initial) of (state.len - parent.len), where parent = states[state.link].

function buildSA(s) {
  const states = [{ len: 0, link: -1, next: {} }]; // state 0 = initial
  let last = 0;

  for (const ch of s) {
    const cur = states.length;
    states.push({ len: states[last].len + 1, link: -1, next: {} });

    let p = last;
    while (p !== -1 && !states[p].next[ch]) {
      states[p].next[ch] = cur;
      p = states[p].link;
    }
    if (p === -1) {
      states[cur].link = 0;
    } else {
      const q = states[p].next[ch];
      if (states[p].len + 1 === states[q].len) {
        states[cur].link = q;
      } else {
        const clone = states.length;
        states.push({ len: states[p].len + 1, link: states[q].link, next: { ...states[q].next } });
        while (p !== -1 && states[p].next[ch] === q) {
          states[p].next[ch] = clone;
          p = states[p].link;
        }
        states[q].link = clone;
        states[cur].link = clone;
      }
    }
    last = cur;
  }
  return states;
}

function countDistinct(states) {
  let total = 0;
  for (let i = 1; i < states.length; i++) {
    const parentLen = states[i].link === -1 ? 0 : states[states[i].link].len;
    total += states[i].len - parentLen;
  }
  return total;
}

// Brute-force verification: enumerate all substrings and count distinct ones.
function bruteForceCount(s) {
  const seen = new Set();
  for (let i = 0; i < s.length; i++)
    for (let j = i + 1; j <= s.length; j++)
      seen.add(s.slice(i, j));
  return seen.size;
}

// Simple layered layout: BFS from state 0.
function layout(states) {
  const W = 420, H = 200, R = 17;
  const layers = [];
  const depth = new Array(states.length).fill(-1);
  depth[0] = 0;
  const queue = [0];
  while (queue.length) {
    const u = queue.shift();
    for (const v of Object.values(states[u].next)) {
      if (depth[v] === -1) { depth[v] = depth[u] + 1; queue.push(v); }
    }
  }
  const maxD = Math.max(...depth);
  const byLayer = [];
  for (let d = 0; d <= maxD; d++) byLayer.push([]);
  depth.forEach((d, i) => byLayer[d].push(i));

  const pos = new Array(states.length);
  const colW = maxD > 0 ? Math.min(80, (W - 2 * R) / maxD) : 80;
  byLayer.forEach((layer, d) => {
    const rowH = H / (layer.length + 1);
    layer.forEach((id, i) => {
      pos[id] = { x: R + d * colW, y: rowH * (i + 1) };
    });
  });
  return { pos, W, H: Math.max(H, byLayer.reduce((m, l) => Math.max(m, l.length), 0) * 36 + 20), R, maxD };
}

function renderSVG(states, s) {
  const { pos, W, H, R } = layout(states);
  const ns = 'http://www.w3.org/2000/svg';
  const svg = document.createElementNS(ns, 'svg');
  svg.setAttribute('class', 'aut');
  svg.setAttribute('viewBox', `0 0 ${W} ${H}`);
  svg.setAttribute('width', W);
  svg.setAttribute('height', H);

  // Arrowhead marker
  const defs = document.createElementNS(ns, 'defs');
  const marker = document.createElementNS(ns, 'marker');
  marker.setAttribute('id', 'arr');
  marker.setAttribute('markerWidth', '6');
  marker.setAttribute('markerHeight', '6');
  marker.setAttribute('refX', '5');
  marker.setAttribute('refY', '3');
  marker.setAttribute('orient', 'auto');
  const poly = document.createElementNS(ns, 'polygon');
  poly.setAttribute('points', '0 0 6 3 0 6');
  poly.setAttribute('fill', '#1d3557');
  marker.appendChild(poly);
  defs.appendChild(marker);
  svg.appendChild(defs);

  // Suffix links (dashed)
  for (let i = 1; i < states.length; i++) {
    const lk = states[i].link;
    if (lk < 0) continue;
    const { x: x1, y: y1 } = pos[i];
    const { x: x2, y: y2 } = pos[lk];
    const line = document.createElementNS(ns, 'line');
    line.setAttribute('x1', x1); line.setAttribute('y1', y1);
    line.setAttribute('x2', x2); line.setAttribute('y2', y2);
    line.setAttribute('stroke', '#adb1b8');
    line.setAttribute('stroke-width', '1');
    line.setAttribute('stroke-dasharray', '3 3');
    svg.appendChild(line);
  }

  // Transitions (solid)
  for (let u = 0; u < states.length; u++) {
    for (const [ch, v] of Object.entries(states[u].next)) {
      const { x: x1, y: y1 } = pos[u];
      const { x: x2, y: y2 } = pos[v];
      const dx = x2 - x1, dy = y2 - y1, dist = Math.hypot(dx, dy);
      if (dist === 0) continue;
      const ex = dx / dist, ey = dy / dist;
      const sx = x1 + ex * R, sy = y1 + ey * R;
      const tx = x2 - ex * (R + 5), ty = y2 - ey * (R + 5);
      const line = document.createElementNS(ns, 'line');
      line.setAttribute('x1', sx); line.setAttribute('y1', sy);
      line.setAttribute('x2', tx); line.setAttribute('y2', ty);
      line.setAttribute('stroke', '#1d3557');
      line.setAttribute('stroke-width', '1.5');
      line.setAttribute('marker-end', 'url(#arr)');
      svg.appendChild(line);
      // Label
      const mx = (sx + tx) / 2, my = (sy + ty) / 2;
      const lbl = document.createElementNS(ns, 'text');
      lbl.setAttribute('x', mx);
      lbl.setAttribute('y', my - 3);
      lbl.setAttribute('font-size', '10');
      lbl.setAttribute('fill', '#333');
      lbl.setAttribute('text-anchor', 'middle');
      lbl.setAttribute('font-family', 'ui-monospace, monospace');
      lbl.textContent = ch;
      svg.appendChild(lbl);
    }
  }

  // States (circles)
  for (let i = 0; i < states.length; i++) {
    const { x, y } = pos[i];
    const circle = document.createElementNS(ns, 'circle');
    circle.setAttribute('cx', x); circle.setAttribute('cy', y);
    circle.setAttribute('r', R);
    circle.setAttribute('fill', i === 0 ? '#e8eef3' : '#d6e4f0');
    circle.setAttribute('stroke', '#1d3557');
    circle.setAttribute('stroke-width', '1.5');
    svg.appendChild(circle);
    const t = document.createElementNS(ns, 'text');
    t.setAttribute('x', x); t.setAttribute('y', y + 4);
    t.setAttribute('font-size', '11');
    t.setAttribute('fill', '#1d3557');
    t.setAttribute('text-anchor', 'middle');
    t.setAttribute('font-family', 'ui-monospace, monospace');
    t.setAttribute('font-weight', '700');
    t.textContent = i;
    svg.appendChild(t);
  }
  return svg;
}

function run() {
  const s = document.getElementById('inp').value.replace(/\s/g, '');
  if (!s) { document.getElementById('stats').innerHTML = ''; document.getElementById('vis').innerHTML = ''; document.getElementById('log').textContent = ''; return; }

  const states = buildSA(s);
  const distinct = countDistinct(states);
  const bf = bruteForceCount(s);
  const maxStates = 2 * s.length - 1;

  document.getElementById('stats').innerHTML =
    fmt('String: <b>%s%</b> (length %length%) &nbsp;|&nbsp; States: <b>%length2%</b> / max %maxStates% &nbsp;|&nbsp; Distinct substrings: <b>%distinct%</b>', { s: s, length: s.length, length2: states.length, maxStates: maxStates, distinct: distinct });

  const vis = document.getElementById('vis');
  vis.innerHTML = '';
  vis.appendChild(renderSVG(states, s));

  const match = distinct === bf ? '✓ matches brute force' : '✗ mismatch!';
  document.getElementById('log').textContent =
    fmt('Brute-force distinct count: %bf% — %match%. Suffix links shown as dashed gray lines. Solid blue arrows = transitions (labeled with character).', { bf: bf, match: match });
  console.log('SA states:', states.length, '| distinct substrings (SA):', distinct, '| brute force:', bf, '| match:', distinct === bf);
}

document.getElementById('build').addEventListener('click', run);
document.getElementById('inp').addEventListener('keydown', e => { if (e.key === 'Enter') run(); });
document.getElementById('reset').addEventListener('click', () => {
  document.getElementById('inp').value = '';
  document.getElementById('stats').innerHTML = '';
  document.getElementById('vis').innerHTML = '';
  document.getElementById('log').textContent = '';
});
run();
Result
Console

Notice two things. First, the number of states grows at most linearly — never more than 2n−12n - 1 for a string of length nn. Second, the distinct-substring count is computed in one linear pass over the automaton; brute-force enumeration would take O(n2)O(n^2) time just to list them. That gap — linear automaton vs quadratic enumeration — is the suffix automaton's superpower.

The Real Complexity

The suffix automaton is proven optimal — no smaller DFA can recognise exactly the substrings of any given string. The bounds are tight and elegant:

  • States: at most 2n−12n - 1. The worst case is achieved by strings like aaa…ab — a run of one character followed by a single different one. Every state corresponds to an equivalence class of substrings that all end at exactly the same set of positions in the original string. These classes are called endpos classes, and partitioning all substrings into endpos classes is what produces the minimal automaton automatically.
  • Transitions: at most 3n−43n - 4. Again tight in the worst case, and again a consequence of the endpos structure.
  • Build time: O(n)O(n). The online algorithm maintains a suffix link tree — a tree of endpos classes — and a pointer to the last created state. Each character extension does a bounded amount of work: follow suffix links, add at most two new states, redirect at most a constant number of transitions.
  • The suffix link is the key insight: every state vv has a link to the state whose endpos class is the smallest proper superset of vv's endpos class. These links form a tree — the suffix link tree — that is also isomorphic to the suffix tree of the reversed string.

The result is a data structure that is simultaneously minimally sized, linearly built, and immediately queryable: pattern search is just one DFA traversal in O(∣P∣)O(|P|) time, optimal by any measure. Compare this with the brute-force approach of enumerating all O(n2)O(n^2) substrings and storing them in a trie — the suffix automaton replaces exponential storage with linear storage while keeping query time constant per character.

Where It Matters

The suffix automaton is not an academic curiosity — it is a workhorse behind several real-world systems:

  • DNA and protein search: genomic databases store sequences hundreds of millions of characters long. Indexing a genome with a suffix automaton (or the related suffix array) lets a query like "does this gene fragment appear anywhere in the genome?" return in microseconds.
  • Longest common substring: given two strings, you can find the longest string that is a substring of both by building the suffix automaton of one and running the other through it while tracking the longest accepted prefix. This runs in O(n+m)O(n + m) time.
  • Counting distinct substrings: the interactive demo above does this; the formula — sum over all states of (longest endpos length − suffix-link-parent's longest length) — gives the exact count in a single DFS.
  • Data compression: the LZ-family of compression algorithms (the basis of ZIP, PNG, and gzip) rely on identifying repeated substrings. Suffix automata make that identification linear.
  • Plagiarism and similarity detection: search engines and academic-integrity tools index documents with suffix structures to find copied passages efficiently.

Whenever the core task is "find or count substrings fast", the suffix automaton (or its close cousin the suffix tree, as in sequence alignment) is the standard choice.

Conclusion

The suffix automaton is one of the most elegant structures in theoretical computer science: a single finite-state machine, provably minimal, built in linear time, that silently encodes every substring of a given string in its transitions.

The size bounds — at most 2n−12n - 1 states, at most 3n−43n - 4 transitions — are not lucky engineering. They flow from the mathematics of endpos equivalence classes, and they cannot be improved. Every time a search engine, a genome browser, or a compression tool needs to find all occurrences of a pattern in a large corpus, it is, directly or indirectly, leaning on this structure.

Knowing the suffix automaton means knowing one of the places where theory and practice meet most cleanly — where the provably optimal solution is also the practically fast one.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/suffix-automaton/Content licensed under CC BY-NC 4.0.