↩ back to Exact Match

Suffix Tree Construction (Ukkonen's Algorithm)

Suffix Tree's own Complexity section names a real, measured cost it doesn't pay off: inserting every suffix into a raw trie and compressing it afterward is O(n²) unconditionally — 5,050 steps for a 100-character text, 320,400 for 800, exactly matching n(n+1)/2 every time, whether or not the suffixes share anything. This page builds the fix that page's own text names but doesn't build: Ukkonen's algorithm constructs the identical compressed tree online, one character at a time, in O(n) total time — not by working harder per suffix, but by noticing that most of the "n suffixes" a naive build inserts one at a time are already implicitly present the moment an earlier one was, and skipping the ones that are.

Try it

Enter a text (lowercase letters, up to 10 characters) and press Build — a $ terminator is appended automatically (see Suffix Tree's own Pitfalls for what skipping it breaks). Press Step to advance one move at a time through the construction: each move is either the active point walking down an already-built edge (free — no character comparison, just arithmetic), a new leaf or split being created, or a phase ending early because the next character already occurs in the tree. The diagram shows the tree exactly as it stands after each move — watch how little of it changes most phases, and how the marked active point jumps around a node it didn't reach by walking down to it.

Why it works

Process the text one character per phase. Phase i is supposed to extend all i+1 suffixes that exist so far — text[0..i], text[1..i], ..., text[i..i] — each by the one new character text[i]. Done naively that's the same n(n+1)/2 total work Suffix Tree's own page measures. Three observations cut that down to O(n):

Rule 1 — extending an existing leaf is free. Every leaf edge's label reaches "to the end of the text so far" by definition; appending a character to the text extends every such label automatically. The implementation makes this literal rather than doing it as work: every leaf's edge end is a shared, mutable reference — one box holding "the current phase index" — instead of a number frozen at the moment the leaf was created. Bump the box once per phase and every existing leaf grows in O(1), however many of them there are.

Rule 3 — extending a suffix that's already there needs no work, and once one extension in a phase hits this, all the shorter ones left in that phase do too. If text[0..i-1] already contains text[j..i] as a substring somewhere, so does every suffix of text[0..i-1] that's at least as long as the point where they diverge — because a shorter suffix's remaining extension is a suffix of a longer one already confirmed present. So the moment one extension in a phase finds its next character already sitting on an edge, the construction stops for that phase immediately, leaving the rest of that phase's suffixes to resolve later once a real distinguishing character shows up (tracked by a pending count, carried into future phases rather than reset to zero). Most phases on ordinary text end almost as soon as they start.

Trick — the active point remembers where the previous extension left off, and a suffix link skips the walk back down. After a phase ends via Rule 3 or after any explicit extension, the algorithm doesn't restart the next suffix's search from the root: it tracks one active point (a node, an edge out of it, and how far along that edge) and, when a new internal node is created by splitting an edge, wires a suffix link from it to whatever node represents the same string with its first character removed — usually not yet known, found on a later split, occasionally the root. Following that link is how the active point jumps from "the place suffix j just needed" to "the place suffix j+1 needs" in O(1), without re-walking character by character from the top.

Put together, the total number of explicit extensions (new leaf, or split) across the whole build has an exact count, not just a bound: it always equals n, the text's own length including the terminator — because every explicit extension, whether it creates a bare leaf or splits an edge first, creates exactly one new leaf as part of doing so, and the finished tree always has exactly n leaves, one per suffix, no more and no fewer. Checked directly across 5,000 random texts of varying length and alphabet size: the count matched the text's own length exactly every time, not merely bounded by it. Measured on Suffix Tree's own worst-case input for its naive build (n copies of the same character): 101, 201, 401, 801 explicit extensions at n = 100, 200, 400, 800 — against that page's own 5,050, 20,100, 80,200, 320,400 on the identical inputs. That input is actually close to this algorithm's cheapest case, not a worst one — Rule 3 fires almost every phase since the next character is always already present, and the whole cascade of real work only happens in the very last phase, once the terminator finally forces every pending suffix apart. The naive build's worst case and this one's are opposite ends of the same axis: repetition that makes character-by-character comparison expensive is exactly the repetition Rule 3 exploits for free.

Reference implementation

This is the exact scheme the demo above steps through — one shared leafEnd box for Rule 1, an active point carried across extensions, and suffix links wiring each freshly split node to where the active point should jump next:

function buildSuffixTreeUkkonen(text) {
  let root;
  const mkNode = (start, end) => ({ start, end, children: new Map(), suffixLink: root, suffixIndex: -1 });
  root = mkNode(-1, { v: -1 });
  root.suffixLink = root;

  const leafEnd = { v: -1 };           // Rule 1: one shared box every leaf edge reads
  let lastNewNode = null;              // most recent split still needing a suffix link
  let activeNode = root, activeEdge = -1, activeLength = 0;
  let remaining = 0;                   // suffixes not yet made explicit this phase or earlier

  const edgeLength = (n) => n.end.v - n.start + 1;

  function walkDown(next) {            // trick: skip down an edge in O(1), no char comparisons
    const len = edgeLength(next);
    if (activeLength >= len) {
      activeEdge += len; activeLength -= len; activeNode = next;
      return true;
    }
    return false;
  }

  for (let pos = 0; pos < text.length; pos++) {
    leafEnd.v = pos;                   // grows every existing leaf edge for free
    remaining++;
    lastNewNode = null;

    while (remaining > 0) {
      if (activeLength === 0) activeEdge = pos;
      const edgeChar = text[activeEdge];

      if (!activeNode.children.has(edgeChar)) {
        // Rule 2: no edge starts here yet -- add a new leaf
        activeNode.children.set(edgeChar, mkNode(pos, leafEnd));
        if (lastNewNode) { lastNewNode.suffixLink = activeNode; lastNewNode = null; }
      } else {
        const next = activeNode.children.get(edgeChar);
        if (walkDown(next)) continue;             // active point lands further in -- retry from there

        if (text[next.start + activeLength] === text[pos]) {
          // Rule 3: next character already occurs here -- nothing to add, stop the phase
          if (lastNewNode && activeNode !== root) { lastNewNode.suffixLink = activeNode; lastNewNode = null; }
          activeLength++;
          break;
        }

        // Rule 2: split the edge, insert the new character, wire a suffix link to the split
        const split = mkNode(next.start, { v: next.start + activeLength - 1 });
        activeNode.children.set(edgeChar, split);
        split.children.set(text[pos], mkNode(pos, leafEnd));
        next.start += activeLength;
        split.children.set(text[next.start], next);
        if (lastNewNode) lastNewNode.suffixLink = split;
        lastNewNode = split;
      }

      remaining--;
      if (activeNode === root && activeLength > 0) {
        activeLength--;
        activeEdge = pos - remaining + 1;
      } else if (activeNode !== root) {
        activeNode = activeNode.suffixLink;              // trick: jump instead of re-walking
      }
    }
  }
  return root;
}

Pitfalls

Freezing a new leaf's end at creation time instead of pointing it at the shared leafEnd box silently truncates every leaf to whatever length it happened to have when it was born — and later phases can't fix it, because nothing about the leaf says it's supposed to keep growing. This is Rule 1 stopped being free and stopped happening at all. On this page's default worked example, Suffix Tree's own "mississippi", searching for "i" against a tree built this way returns [10, 10] — a duplicate, phantom occurrence, not just a wrong count — against the correct [1, 4, 7, 10]; "ssi" returns nothing at all against the correct [2, 5]. The smallest possible case shows the mechanism directly: "aa$" searched for "a" finds only [1], missing position 0 — the leaf created for suffix 0 froze at length 1 ("a") the instant it was made, in the very first phase, and never grew to "aa$" the way the correct shared-box version does. Checked broadly, not just on these examples: across 20,000 random (text, pattern) trials, this variant disagrees with a brute-force scan on 99.8% of them.

Treating Rule 3 like Rule 2 — letting the loop fall through to decrement the pending count and follow a suffix link, instead of stopping the phase immediately — silently abandons every suffix still waiting behind the one Rule 3 just resolved. Rule 3's whole justification is that all the remaining pending suffixes this phase are also already present, not just the one just checked; skipping the early stop makes the loop treat only that one suffix as resolved and move on as if the others had been handled too, when nothing was ever inserted for them. They're not merely delayed — the pending count that would have let a later phase catch them up is now wrong, so some suffixes never get explicit leaves at all. On "mississippi$" searching "ssi": correct is [2, 5], this variant finds only [2], silently losing the second occurrence. The minimal case: "aa$" searched for "a" again finds only [1], the same visible symptom as the frozen-leaf bug above but from an unrelated cause — both here happen to drop the earlier occurrence, but querying "aa$" for ""-adjacent patterns on longer inputs distinguishes them (the frozen-leaf variant duplicates entries; this one only ever omits them). Checked across the same 20,000 random trials: 80.2% disagree with brute force.

Complexity

Time: O(n) total — measured directly above as exactly n explicit extensions, every time, not merely bounded by it: 101, 201, 401, 801 at n = 100, 200, 400, 800, against Suffix Tree's own n(n+1)/2 naive figure on the identical input. The argument holds regardless of how work distributes across phases: every explicit extension creates exactly one new leaf, whether directly or as part of a split, and the finished tree always has exactly n leaves — one per suffix, guaranteed distinct by the terminator — so the while (remaining > 0) loop above does real work exactly n times across the whole build, full stop. Each individual walkDown call is O(1) (arithmetic against already-known edge lengths, no character re-comparison), and the number of suffix-link jumps is bounded the same way the explicit extensions are. Space: O(n) — the same 2n−1 node bound as the resulting tree, plus one suffix-link pointer per internal node.

The tree this page builds is byte-for-byte the same structure Suffix Tree's own naive-build-then-compress produces — checked directly across thousands of random texts by serializing both trees' edge structure and comparing, not just asserted — and every query that page's own reference implementation runs works unmodified against it. This page is a faster path to that same structure, the same relationship Suffix Array Construction (Prefix Doubling) has to Suffix Array. See Choosing an Exact-Match String Matcher for how Suffix Tree itself weighs against the other exact-match entries; this page is a refinement on that comparison, not a new branch in it.