Proofs: Ukkonen's algorithm

Ukkonen's algorithm keeps the implicit suffix tree and runs in linear time full

This proof shows: correctness, termination, complexity.

Let $t = t[0 \ldots N-1]$ with $N = n + 1$ and $t[n] = \$$ not in $t[0 \ldots n-1]$. For $j \ge 0$ let $P_j = t[0 \ldots j-1]$. The implicit suffix tree $\mathcal{I}_j$ is the compact trie of the suffixes of $P_j$: the trie of these strings with every node removed that has one child and is neither the root nor the end of a string that is not a proper prefix of another one. A suffix of $P_j$ is open if it is not a proper prefix of another substring of $P_j$ that extends it, that is, if it occurs in $P_j$ only as a suffix; open suffixes are exactly those that end at leaves.

Lemma 1 (suffix closure). If a string $x$ occurs in $P_j$, every suffix of $x$ occurs in $P_j$. If a suffix $y$ of $P_j$ is not open (it occurs earlier too), then every shorter suffix of $P_j$ is not open. Proof. The first is clear. For the second, $y$ occurs at some position other than the end, followed by a symbol; a suffix $y'$ of $y$ occurs at the corresponding place, followed by the same symbol. $\square$

So the suffixes of $P_j$ split into open ones, the longest, and non-open ones, the shortest, including the empty suffix. Let $r_j$ be the number of non-open nonempty suffixes; they are $t[j - r_j \ldots j-1], \ldots, t[j-1 \ldots j-1]$.

Lemma 2 (once a leaf, always a leaf). An open suffix $t[i \ldots j-1]$ of $P_j$ becomes $t[i \ldots j]$, an open suffix of $P_{j+1}$. Proof. If $t[i \ldots j]$ occurred elsewhere in $P_{j+1}$, then $t[i \ldots j-1]$ would occur in $P_j$ followed by a symbol. $\square$

Lemma 3 (suffix links exist). In $\mathcal{I}_j$, if $cx$ labels an inner node other than the root, then $x$ labels an inner node or the root. Proof. $cx$ is followed in $P_j$ by two distinct symbols, and so is $x$. $\square$

Invariant. At the start of phase $j$ (line L3): (U1) the tree with open leaf edges ending at $j$ is $\mathcal{I}_j$, and each leaf is labeled with the start of its suffix; (U2) $remainder = r_j$; (U3) the active point is the place of $t[j - r_j \ldots j-1]$ (the root if $r_j = 0$), and when $length > 0$, $t[edge \ldots edge + length - 1]$ is the string from $node$ to the active point; (U4) every inner node other than the root has a suffix link to the node of its label without the first symbol.

Initially $j = 0$, the tree is the root, $r_0 = 0$, and all of (U1) to (U4) hold.

One phase. Let $c = t[j]$. Line L3 increases $remainder$ to $r_j + 1$, counting the new empty-plus-$c$ suffix: the strings to be extended by $c$ without a leaf are $x_k = t[j - k \ldots j-1]$ for $k = r_j, \ldots, 0$, and line L4 handles them from the longest. The open suffixes are extended by $c$ through their open leaf edges, without work, and stay open by Lemma 2.

Consider a pass with $remainder = k + 1$, the active point at the place of $x_k$ (by (U3), adjusted below). Lines L5 and L8 bring the active point to a canonical form, where $length$ is less than the length of the edge it is on; line L8 is correct without reading symbols because, by (U3), $x_k$ is spelled from the root, so the edge into $w$ matches the next $|label(w)|$ symbols of $x_k$.

• If $c$ follows the place of $x_k$ (line L9), then $x_k c$ occurs in $P_j$, so it is not open in $P_{j+1}$, and by Lemma 1 none of $x_{k-1} c, \ldots, x_0 c$ is open either; all of them are spelled in the tree by Lemma 1. Nothing is added. The non-open suffixes of $P_{j+1}$ are $x_k c, \ldots, x_0 c$, so $r_{j+1} = k + 1 = remainder$ (U2), and $length + 1$ moves the active point to the place of $x_k c$ (U3).
• Otherwise $x_k c$ does not occur in $P_j$, so it is a new open suffix of $P_{j+1}$, and it needs a leaf. If the place is a node, line L7 adds the leaf; if it is inside an edge, line L10 splits the edge at that place with a new node $u$, whose label $x_k$ is now followed by $c$ and by the old next symbol, so $u$ is a valid branching node, and adds the leaf. In both cases the trie stays compact. The leaf is for the suffix that starts at $j - k = j - remainder + 1$.

After line L11, $remainder = k$, and the next string to handle is $x_{k-1}$, which is $x_k$ without its first symbol. If $node$ is the root, its place is found by dropping the first symbol of the string $t[edge \ldots edge + length - 1]$ from the root, which line L12 does (the new string starts at $j - remainder + 1 = j - k + 1$ and has length $length - 1$). Otherwise $node$ is an inner node whose label is a prefix $cy$ of $x_k$, and by (U4) its link is the node of $y$; the active point $(link(node), edge, length)$ then spells $y$ followed by the same $length$ symbols, which is $x_{k-1}$. If $node$ was the root and $length = 0$, then $x_k$ was empty ($k = 0$) and the loop ends.

If the loop ends because $remainder = 0$, then all of $x_{r_j} c, \ldots, x_0 c$ became leaves, every suffix of $P_{j+1}$ is open except the empty one, $r_{j+1} = 0$, and the active point is the root.

Suffix links (U4). A node $u$ created in line L10 for $x_k$ is an inner node of $P_{j+1}$ with label $x_k$, $|x_k| \ge 1$. If $|x_k| = 1$, its link is the root, which line L12 then reaches: the next pass is at the root and either adds a leaf at the root (line L7, which sets $link(u) \leftarrow$ root) or stops by rule 3 at the root (line L9, same). If $|x_k| \ge 2$, the next pass handles $x_{k-1}$, the label of $u$ without its first symbol: it either finds a node there (rule 3 at a node, or rule 2 at a node, line L7), or creates one by a split (line L10); in each case it sets $link(u)$ to that node, which is the node of $x_{k-1}$, as Lemma 3 requires. The pass handles the place of $x_{k-1}$ exactly, so it cannot be a different node. So at the end of the phase every new inner node has its link, except possibly the last one, whose next pass must exist: the last node is created at $remainder \ge 2$ (at $remainder = 1$ the active point is the root, $x_0$ is empty, and line L7 runs, not line L10), so one more pass follows in the same phase.

End. After phase $n$, with the sentinel, no nonempty suffix of $t$ occurs twice, since each ends with the only $\$$. So $r_N = 0$, all $N$ nonempty suffixes are open and end at leaves, and $\mathcal{I}_N$ is the suffix tree of $t$.

Time. Each pass of the inner loop either breaks (once per phase, at most $N$ times) or creates a leaf. Leaves are never removed (Lemma 2), and there are at most $N$ of them, so there are at most $2N$ passes. Define the node depth $d(v)$ as the number of nodes on the path from the root to $v$, the root excluded. For an inner node $v$ with label $cy$, each ancestor $a \ne$ root of $v$ has label $cy'$ with $y'$ a prefix of $y$, and its link, the node of $y'$, is an ancestor of the node of $y$ or the root, distinct for distinct $a$ (the labels $y'$ differ), except that the ancestor with label $c$ links to the root. So $d(link(v)) \ge d(v) - 1$. Line L13 lowers the active node depth by at most 1, line L12 does not change $node$, a split changes no node depth of the active node, and each step of line L8 raises it by 1. The node depth is at most $N$ at all times, starts at 0, and drops by at most $1$ in each of the at most $2N$ passes, so the number of steps of line L8 is at most $N + 2N = 3N$. Each step takes $O(1)$ time with constant-time child lookup. So the total time is $O(N) = O(n)$, and the algorithm terminates. $\blacksquare$