The idea: all suffixes in one compressed trie

Take a text S of length n and end it with a character that occurs nowhere else, $. Its suffixes are S[0..], S[1..], …, down to $. Put them all in one trie, then merge every chain of single-child nodes into one edge. The result is the suffix tree.

The suffix tree of banana$. The root has four edges: $ to leaf 6, a to node a, banana$ to leaf 0, and na to node na. Node a has edges $ to leaf 5 and na to node ana; node ana has $ to leaf 3 and na$ to leaf 1. Node na has $ to leaf 4 and na$ to leaf 2. Blue suffix links go from ana to na and from na to a.
The suffix tree of banana$: seven leaves, one per suffix, three internal nodes, and the suffix links ana → na → a.
  • Each leaf is one suffix. The number in it is where the suffix starts.
  • Each internal node has at least two children, so there are at most n − 1 of them.
  • The edges out of a node start with different characters, so a walk down the tree never has to choose.
  • Reading the edge labels from the root to a leaf spells that leaf's suffix.

The $ makes sure no suffix is a prefix of another one, so every suffix really ends at a leaf.

Edges are index pairs

The edge labels together can be O(n²) characters long. The tree does not store them. An edge stores two numbers, [start, end), that point into S: the edge na$ of banana$ is [4, 7). So the whole tree takes O(n) space. The canvas prints the characters so they are easy to read, and cuts long labels with “…”.

Ukkonen's algorithm: one character at a time

The naive way inserts each suffix from the root and takes O(n²) time. Esko Ukkonen (1995) builds the tree online, left to right, in O(n). Phase i adds S[i] to the end of every suffix so far. Adding a character to one suffix is an extension, and it follows one of three rules:

rulewhenwhat happens
1the suffix ends at a leafthe leaf edge gets one character longer
2the next character is missingadd a leaf; if the suffix ends inside an edge, split the edge first and make a new internal node
3the next character is already therenothing: the suffix is already in the tree, hidden in an edge

Three tricks make the whole build linear.

Trick 1: one global end for all leaves

Once a suffix ends at a leaf, it stays a leaf, and every later phase only applies rule 1 to it. So a leaf edge does not store its own end. It stores [start, #), and # is one shared variable, end. Setting end = i + 1 at the start of phase i grows every leaf at once, in constant time. On the canvas, every leaf label gets one character longer at the start of each phase.

Trick 2: the active point and the remainder

Rule 3 is a showstopper. If S[i] already follows the longest waiting suffix, it also follows every shorter one, so the phase can stop right there. The suffixes that were not inserted wait for later phases. Two variables keep track of them:

  • remainder: how many suffixes still have to be inserted. The canvas tints them in the text row.
  • The active point (active node, active edge, active length): where the longest waiting suffix ends in the tree. It is drawn as a red ring on the node and a red dot on the edge.

In banana$ the phases for a, n, a (i = 3, 4, 5) all stop on rule 3, and remainder grows to 3. The last phase, $, is new everywhere, so it inserts all four waiting suffixes and makes the three internal nodes (Demo 1). With aaaa$, every phase after the first stops on rule 3, and the $ phase does all the splits (Demo 3). Without the $, those suffixes would stay hidden inside edges: that tree is called an implicit suffix tree.

If the active length reaches past the end of the active edge, the active point walks down to the next node and the length drops by the edge length. Because an edge is skipped as a whole, this costs one step per node, not per character (“skip/count”).

After an insert, the next waiting suffix is one character shorter: if the last one was xα, the next is α. At the root this is easy: active length − 1, and the active edge starts one character later. At an internal node for xα, the algorithm jumps along that node's suffix link to the node for α, and keeps the same edge and length. No walk from the root is needed.

The last phase of banana$ in three panels. 1: inserting ana$ splits the edge anana$ after ana, making node ana with leaves 3 ($) and 1 (na$). 2: inserting na$ splits nana$ after na, making node na with leaves 4 and 2, and a blue suffix link goes from ana to na. 3: inserting a$ splits the edge to ana after a, making node a with leaf 5, and a suffix link goes from na to a.
The $ phase of banana$ makes three splits in a row. Each new internal node gets its suffix link from the next one: ana → na, then na → a.

A suffix link is set when it is needed: when a phase creates an internal node, the next extension of the same phase ends at the node for the string one shorter, and the link from the previous new node points there. Nodes with no drawn link point to the root. In abcabxabcd$ the active point walks down to ab and then jumps along the link ab → b (Demo 2).

Why linear: each phase adds one to remainder and every extension takes one away, so there are at most n extensions in total. The walk-downs are paid for by the active length, which grows by one per phase. The final counts at the end of each demo show it: banana$ needs 3 splits and 3 rule-3 stops for 7 characters.

for i in 0 .. n-1:
    end = i + 1;  remainder += 1;  lastNew = none
    while remainder > 0:
        if activeLength == 0:  activeEdge = i
        if active node has no edge for S[activeEdge]:
            add leaf i-remainder+1;  link lastNew → active node
        else if activeLength ≥ length of that edge:
            walk down;  continue
        else if S[i] follows the active point:
            activeLength += 1;  link lastNew → active node;  break      # rule 3
        else:
            split the edge, add leaf;  link lastNew → split;  lastNew = split
        remainder -= 1
        if active node is root and activeLength > 0:
            activeLength -= 1;  activeEdge = i - remainder + 1
        else:
            active node = suffix link of active node (or root)

Every substring of S is a prefix of some suffix, so it is a path from the root. To find a pattern of length m, walk down, matching one character at a time. That takes O(m) time, however long the text is. Every leaf below the end point is one occurrence. In banana$, ana ends at node ana, which has leaves 1 and 3 below it (Demo 1); issi in mississippi$ is found at 1 and 4 (Demo 4); nab stops after na, because node na has no b edge (Demo 5).

Other questions become tree walks: the longest repeated substring is the deepest internal node (ana in banana$, issi in mississippi$); the number of distinct substrings is the total length of all edges; the longest common substring of two strings comes from a tree of both. A suffix array plus its LCP array answers the same questions with about a quarter of the memory, which is why it is used more in practice. For many patterns in one text pass, see Aho-Corasick; for one pattern with no index, see KMP.

What the page leaves out

The page uses small fixed texts and the lowercase letters. Real implementations store children in arrays, hash maps or sorted lists to trade memory against speed, and need about 10 to 20 bytes per text character. The page does not draw suffix links to the root, leaf suffix links, or generalized suffix trees of several strings. It also leaves out McCreight's and Weiner's earlier linear-time algorithms, building from a suffix array, and suffix automata.