Proofs: LCP interval tree

The stack scan builds the lcp-interval tree full

This proof shows: correctness, termination, time.worst.

Notation. $T = T[0 \ldots n-1]$, 0-based, no sentinel; a proper prefix sorts first. $S_r = T_{SA[r]}$ is the suffix of rank $r$, $LCP[r] = \mathrm{lcp}(S_{r-1}, S_r)$ for $1 \le r < n$, and for the definitions $LCP[0] = LCP[n] = -1$. The end of a suffix counts as a symbol smaller than all others, so two different suffixes always differ at some depth. By the LCP-RMQ lemma, $\mathrm{lcp}(S_a, S_b) = \min LCP[a+1 \ldots b]$ for $a < b$. An $\ell$-interval and its $\ell$-indices are as on the page; for an interval $v$, $k_1(v)$ is its first $\ell$-index. The root is $[0, n-1]$ with value 0.

Lemma 1 (intervals are branching substrings). For $\ell > 0$, $[i, j]$ is an $\ell$-interval if and only if it is the set of ranks of the suffixes that start with some $u$ of length $\ell$ that is followed in $T$ by two different symbols (the end counts). In particular two lcp-intervals are nested or disjoint, and two different $\ell$-intervals with the same $\ell$ are disjoint.

Proof. The suffixes that start with a given $u$ have consecutive ranks. ($\Rightarrow$) By condition 2 and the lemma, all $S_r$ with $i \le r \le j$ start with the same $u$ of length $\ell$, and at an $\ell$-index $k$, $S_{k-1}$ and $S_k$ differ at depth $\ell$. By conditions 1 and 3, $S_{i-1}$ and $S_{j+1}$, if they exist, do not start with $u$. ($\Leftarrow$) Let $[i, j]$ be the ranks of the suffixes that start with $u$; two of them differ at depth $\ell$, so $i < j$, all of $LCP[i+1 \ldots j]$ are at least $\ell$, and the minimum between those two is exactly $\ell$. $LCP[i] < \ell$ and $LCP[j+1] < \ell$ because the neighbors do not start with $u$. The last claim follows: for $u$ and $u'$, the sets are nested if one is a prefix of the other and disjoint otherwise. $\square$

Lemma 2 (children). Let $v = [i, j]$ have value $\ell$ and $\ell$-indices $k_1 < \cdots < k_r$ (for the root, the 0-indices, possibly none). Each range $[i, k_1 - 1], \ldots, [k_r, j]$ is a single rank or an lcp-interval of value larger than $\ell$, and every lcp-interval strictly inside $v$ lies inside one of them. So the lcp-intervals form a tree under containment, and these ranges are the children.

Proof. In a range $[a, b]$ with $a < b$, the values $LCP[a+1 \ldots b]$ exceed $\ell$; let $\ell'$ be their minimum. $LCP[a]$ is $LCP[i] < \ell$ or an $\ell$-index value $\ell$, and $LCP[b+1]$ is an $\ell$-index value or $LCP[j+1] < \ell$, so both are below $\ell'$: $[a, b]$ is an $\ell'$-interval. An interval $w = [a', b'] \subsetneq v$ of value $\ell''$ cannot have an $\ell$-index $k$ in $(a', b']$: then $\ell'' \le \ell$, and $LCP[a'] < \ell'' \le \ell$ forces $a' = i$, and in the same way $b' = j$, so $w = v$. $\square$

Invariant. At the start of the iteration with index $i$ ($1 \le i \le n$), the stack holds, from the bottom, the root and the lcp-intervals $v$ with $k_1(v) \le i - 1 \le rb(v)$, in order of increasing value, each with its correct $lb$; and $kids(v)$ lists, in rank order, the child intervals $c$ of $v$ with $rb(c) \le i - 2$. These intervals all contain rank $i - 1$, so by Lemma 1 they are nested, and their values are different, which gives the strict order.

For $i = 1$, no interval has $k_1 \le 0$, the stack is the root, and no lists are filled. Assume the invariant at $i$, and let $h = LCP[i]$ for $i < n$ and $h = 0$ for $i = n$. For an interval other than the root, $h = 0$ acts as $LCP[n] = -1$, since all their values are positive.

Step 1 (pops). An interval on the stack contains $i - 1$. If its value is greater than $h$, it does not contain $i$ (else $LCP[i]$ would be at least its value), so $rb = i - 1$, which line L5 records. If its value is at most $h$, it contains $i$, since $rb = i - 1$ would need $LCP[i]$ below its value. So L4 and L5 pop exactly the intervals that end at $i - 1$, and the others still satisfy $k_1 \le i \le rb$.

Step 2 (push). The intervals with $k_1(v) = i$ have value $h = LCP[i]$; there is at most one, the $h$-interval $H = [a, b]$ that contains $i$, and only if $k_1(H) = i$. Line L7 pushes if and only if this $H$ exists. If $k_1(H) = i$, $H$ was not on the stack, and the top after the pops contains $i$ with a value at most $h$; it is not $H$, so its value is less than $h$. Conversely, if the top has a value less than $h$ and $h > 0$, the $h$-interval that contains $i - 1$ and $i$ is not on the stack (it would lie above the top and not be popped), so its first $h$-index is $i$.

Its left end is correct. Here $a = \max \{ a' < i : LCP[a'] < h \}$. If $a = i - 1$, then $LCP[i-1] < h$. A popped interval $Q$ ends at $i - 1$ and starts before it, so $LCP[i-1] \ge value(Q) > h$; hence nothing is popped, and $lb = i - 1$ from line L3. If $a < i - 1$, then $LCP[a+1 \ldots i-1] > h$, since $k_1(H) = i$; with $g$ their minimum, $G = [a, i - 1]$ is a $g$-interval with $k_1(G) \le i - 1$, on the stack and popped. The last interval $P$ popped has the smallest value among the popped ones, so $G \subseteq P$; and $P \subsetneq H$, as both contain $i - 1$ and $P$ has the larger value. So $a \le lb(P) \le lb(G) = a$, and line L5 left $lb = lb(P) = a$.

Step 3 (children). Let $c$ be popped, and $p$ its parent in the tree of Lemma 2. Then $c$ is the child range of $p$ that ends at $i - 1$: either $rb(p) = i - 1$, or $i$ is a $value(p)$-index and $h = value(p)$. If $p$ is on the stack, it is the interval just below $c$, since the stack is a chain under containment; and $h \le value(p)$ in both cases (in the first, $p$ ends at $i - 1$ and is popped next, or is the root at $i = n$ with $h = 0$). Line L6 appends $c$ to $kids(p)$. If $p$ is not on the stack, then $k_1(p) > i - 1$; $p$ has an $\ell$-index before every child that is not its first, so $c$ is its first child and $k_1(p) = i$, that is, $p = H$. The interval below $c$ is then a proper ancestor of $H$ with a value less than $h$, so line L6 keeps $c$ as $last$, the loop stops, and line L8 makes $c$ the first child of $H$. In all cases $c$ joins its parent's list after the children that closed earlier, so the lists are in rank order.

So the invariant holds at $i + 1$. At $i = n$, every interval other than the root is popped and none is pushed, and line L9 sets $rb(root) = n - 1$. By Lemma 2 and the invariant, each lcp-interval was pushed once, at $i = k_1$, closed with its correct ends, and attached to its parent. For $n \le 1$ the loop pushes nothing and the tree is the root.

Theorem (time). The build runs in $O(n)$ time, and there are at most $n - 1$ intervals besides the root.

Proof. Each iteration pushes at most one interval, at an index $i \le n - 1$, so there are at most $n - 1$ pushes, at most as many pops, and $O(1)$ work besides. The loop has $n$ iterations, so it ends. $\blacksquare$