↩ back to Exact Match

Suffix Tree

Suffix Array already flips exact match around: preprocess the text once, then answer any future pattern with a binary search instead of a fresh scan. A suffix tree keeps that same inversion but changes the mechanism underneath it. Instead of sorting suffixes into a flat array and binary-searching over them, it builds every suffix into one shared, edge-compressed trie, so a query walks straight down from the root, one pattern character at a time, and never compares against other suffixes at all. That drops the O(log n) factor Suffix Array's binary search pays on every query — a suffix tree answers in O(m), the pattern's own length, full stop. The cost is a heavier structure: real nodes and child pointers instead of an array of n plain integers, and a naive build that's unconditionally O(n²), not just slow on adversarial text the way Suffix Array's naive sort is.

Try it

Enter a text (lowercase letters only, up to 12 characters) and press Build to insert every suffix into a trie and compress it — the tree below shows each branch point as a dot and each leaf as the position where that suffix starts. With append $ terminator checked (the default), a sentinel character is added to the end first; uncheck it to see what breaks (see Pitfalls). Then enter a pattern and step through the search: the walk follows one child edge per pattern character, comparing the edge's label against the pattern as it goes, until either an edge is missing (no match) or the whole pattern is consumed (match — every leaf in the subtree below that point is one occurrence).

Why it works

Insert every suffix of the text into a trie, one character per edge: any two suffixes that share a prefix walk the identical path for as long as that shared prefix lasts, branching apart only at the first character where they differ. That's already enough to answer a query correctly — walk the pattern character by character from the root, following whichever child edge starts with the next expected character. If the walk runs out of matching edges partway through the pattern, the pattern doesn't occur anywhere, full stop. If it consumes the whole pattern instead, every suffix reachable from that point on shares the pattern as a prefix by construction — so collecting every leaf in the subtree below it reads off every occurrence, no separate scan needed.

A raw trie built this way wastes a node for every character of every unshared suffix tail — most of it is long, non-branching chains where each node has exactly one child. A suffix tree collapses each such chain into a single edge labeled with the whole substring it represents, so what remains has exactly one node per real branch point plus one leaf per suffix — at most 2n−1 nodes total for n suffixes, however long the text actually is (checked directly: 5,000 random builds up to length 12, zero violations of that bound, and the no-sharing case — every suffix starting with a different character — reaches it exactly). A query still only ever touches real branch points, comparing each edge's label against the corresponding stretch of the pattern one character at a time.

Reference implementation

This is the exact scheme the demo above steps through — build the raw trie, compress non-branching chains into single edges, then walk a query down it:

function buildTrie(text) {
  const root = { children: new Map(), isLeaf: false, start: -1 };
  for (let i = 0; i < text.length; i++) {
    let node = root;
    for (let j = i; j < text.length; j++) {
      const ch = text[j];
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), isLeaf: false, start: -1 });
      node = node.children.get(ch);
    }
    node.isLeaf = true;
    node.start = i; // this suffix started at text position i
  }
  return root;
}

function compress(node) {
  const edges = new Map(); // first char -> { label, target }
  for (const [ch, child] of node.children) {
    let label = ch, cur = child;
    while (cur.children.size === 1 && !cur.isLeaf) {
      const [[onlyCh, onlyChild]] = cur.children;
      label += onlyCh;
      cur = onlyChild;
    }
    const compressedChild = compress(cur);
    compressedChild.start = cur.start;
    compressedChild.structuralLeaf = cur.children.size === 0;
    edges.set(ch, { label, target: compressedChild });
  }
  return { edges, structuralLeaf: node.children.size === 0 };
}

function collectOccurrences(node, out) {
  if (node.structuralLeaf) out.push(node.start);
  for (const [, e] of node.edges) collectOccurrences(e.target, out);
}

function query(tree, pattern) {
  let node = tree, i = 0;
  while (i < pattern.length) {
    const edge = node.edges.get(pattern[i]);
    if (!edge) return []; // no edge starts with this character -- no match
    const label = edge.label;
    let k = 0;
    while (k < label.length && i < pattern.length) {
      if (label[k] !== pattern[i]) return []; // edge diverges from the pattern
      k++; i++;
    }
    if (i === pattern.length) {
      const out = [];
      collectOccurrences(edge.target, out);
      return out.sort((a, b) => a - b);
    }
    node = edge.target;
  }
  return [];
}

Pitfalls

Skipping the $ terminator silently undercounts real occurrences, and it's a genuinely common mistake, not a contrived one. collectOccurrences above counts structural leaves — nodes with no children — under the matched point. That's the natural way to write it, and it's exactly correct whenever every suffix is guaranteed to end at a node of its own. Appending a sentinel character that appears nowhere else in the text guarantees exactly that: no suffix of text + "$" can ever be a prefix of another, since they all end in the same unique, otherwise-absent character. Without it, a short suffix that happens to be a prefix of a longer one ends up sharing a node with that longer suffix's path instead of getting a leaf of its own — and collectOccurrences, only ever looking at structural leaves, walks straight past it. On this page's own default example, "mississippi" searched for "i": with the terminator, the demo finds all four real occurrences — positions 1, 4, 7, 10. Without it, the suffix "i" itself (starting at position 10) is a prefix of the suffix "ississippi" (starting at position 1), so its insertion path ends at a branch node that keeps going rather than a leaf — the demo reports only 1, 4, 7, silently missing position 10. Checked, not just claimed: across roughly 15,400 valid random (text, pattern) pairs, appending the terminator matched brute-force search exactly every time (0 mismatches); skipping it produced 782 mismatches, about 5.1% of pairs — not a rare edge case.

The naive build above is O(n²) unconditionally — every text, not just repetitive or adversarial ones. Unlike Suffix Array's naive sort, whose quadratic blowup is a property of the input (repeated characters make comparisons expensive), this page's cost is a property of the construction method alone: inserting the suffix starting at position i always walks or creates n−i nodes, whether or not that path already exists, so total work is n + (n−1) + … + 1 = n(n+1)/2 — always, exactly, provably, for every text of length n. Measured directly on a repeated- character string as n doubles: 5,050, 20,100, 80,200, 320,400 construction steps at n = 100, 200, 400, 800 — each doubling roughly quadruples the cost, the signature of quadratic growth, matching the closed-form formula exactly at every size. How much of that raw work survives into the final tree depends entirely on how much the suffixes actually share: "mississippi$" (78 steps) shares enough to need only 66 raw trie nodes, compressing down to 19; a string with no two characters alike, like "abcdefghijkl$" (91 steps), shares nothing at all — every step creates a new node, 92 of them, right up against the theoretical ceiling. Real suffix tree construction fixes the build cost, not just the final size: Ukkonen's algorithm builds the identical compressed tree online in O(n) total time using suffix links to jump between insertion points instead of re-walking from the root each time — not implemented on this page, which builds the raw trie and compresses it afterward for clarity.

Complexity

Time: as shipped, construction inserts n suffixes into a raw trie and compresses it, O(n²) unconditionally (measured directly above, not just asserted) — Ukkonen's algorithm achieves the same tree in O(n) but isn't implemented here. Each query after that costs O(m): one edge lookup and up to O(edge length) character comparisons per pattern character consumed, summing to at most m total character comparisons across the whole walk, with no O(log n) factor from searching over n suffixes the way Suffix Array's binary search does — plus O(k) more to walk the subtree and read off all k occurrences. Space: O(n) — at most 2n−1 nodes for n suffixes (checked directly above), but each node is a real object with a children map and an edge label substring, not a plain integer the way Suffix Array's array entries are — the asymptotic bound matches, the constant factor per unit of space does not.

The other five exact match entries that aren't Suffix Array all pay their search cost against the text fresh, every time a pattern is checked — see that page's own Complexity section for the full contrast. Suffix Array and this page both index the text once and answer any number of later patterns cheaply; between the two, this page trades a heavier structure and a slower unconditional build for a query that never pays a log factor. See Choosing an Exact-Match String Matcher for the full comparison across all ten.