Proofs: Sparse suffix tree

The sparse suffix tree is the compacted trie of the chosen suffixes, and its searches report the right positions full

This proof shows: correctness, complexity.

We use the pseudocode, the notation and the invariant (P1) to (P3) of the page. Let $T' = T\$$, let $s_1 < s_2 < \cdots < s_b$ be the chosen suffixes of $T'$ in lexicographic order (written by their positions), and let $h_t = lcp(s_{t-1}, s_t)$ for $t \ge 2$, $h_1 = 0$. Because $\$$ occurs only at the end, no chosen suffix is a prefix of another.

Lemma 1 (stack). After the suffix $s_t$ is processed, the stack holds the path from the root to the leaf of $s_t$ in the compacted trie $C_t$ of $s_1, \ldots, s_t$, and the tree built so far is $C_t$.

Proof. By induction on $t$. For $t = 1$ the leaf of $s_1$ is attached to the root, which is $C_1$. Let it hold for $t - 1$. In $C_t$, the leaf of $s_t$ hangs from the node of depth $h_t$ on the path to $s_{t-1}$: the suffixes $s_1, \ldots, s_{t-1}$ are smaller than $s_t$, and the one with the longest common prefix with $s_t$ among them is $s_{t-1}$, since a string between two others in sorted order shares at least their common prefix with the larger one. So $s_t$ leaves the path to $s_{t-1}$ at depth $h_t$, and it shares no longer prefix with any earlier suffix. Line L2 pops the nodes of depth greater than $h_t$ from that path. If the top has depth exactly $h_t$, the leaf hangs from it. Otherwise the last popped node lies below depth $h_t$ on an edge from the top, and line L3 splits this edge at depth $h_t$, using the representative of the popped node to spell the label, which is correct since that node's string extends the top's string along the path. Line L4 attaches the leaf with the label $T'[s_t + h_t \ldots]$; its first symbol differs from $s_{t-1}$ at depth $h_t$, and the later siblings, from suffixes after $s_t$, are not there yet, so the children keep distinct first symbols. The nodes of the new path are on the stack. $\square$

At the end the tree is $C_b$: (P1) holds by the leaves attached, (P3) holds by the labels, and (P2) holds because a node created by line L3 receives the popped node and the new leaf, and the root and other nodes only gain children. A tree with $b$ leaves where each internal node except the root has at least two children has at most $b - 1$ internal nodes besides the root, so at most $2b - 1$ nodes besides the root.

SEARCH. By (P2) and (P3), the walk of line L5 follows the unique path that spells a prefix of $P$, and it fails exactly when no node string, and thus no chosen suffix, extends a string that $P$ starts with, so then no chosen suffix has prefix $P$. If it succeeds, the point where $P$ ends lies on the edge into a node $x$ (or at $x$), and the chosen suffixes with prefix $P$ are exactly the leaves below $x$, by (P1) and (P3). Line L6 returns them. The walk compares at most $m$ symbols, and the subtree of $x$ has fewer than $2z$ nodes for $z$ leaves, by the bound above, so the time is $O(m + z)$.

SEARCH-ALL. Let the chosen positions be $0, k, 2k, \ldots$ below $n$, and $m \ge k$. Every reported position is an occurrence: if $j$ is a chosen position where $P[r \ldots]$ occurs and $T[j - r \ldots j - 1] = P[0 \ldots r - 1]$, then $P$ occurs at $j - r$. Every occurrence is reported: let $P$ occur at $i$, and let $j$ be the smallest multiple of $k$ with $j \ge i$, so $r = j - i < k \le m$. Then $j < i + m \le n$, so $j$ is a chosen position, $P[r \ldots]$ is nonempty and occurs at $j$, and SEARCH reports $j$ for this $r$; the check of line L8 succeeds, and $i = j - r$ is reported. No position is reported twice: a position $i$ is reported only for $r = j - i$ with $j$ the chosen position in $[i, i + k)$, which is unique. $\blacksquare$