Proofs: Farach's algorithm

Farach's algorithm computes the suffix array and the LCP array in linear time full

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

Notation. $T' = T'[0 \ldots N-1]$ with symbols in $\{1, \ldots, \sigma\}$ at positions $0$ to $N - 2$ and $T'[N-1] = 0$, the sentinel. Positions are 0-based, $T'_p = T'[p \ldots N-1]$, and the order is lexicographic. Since the sentinel is unique and smallest, two different suffixes are never prefixes of each other: for $x \ne y$, with $h = \mathrm{lcp}(T'_x, T'_y)$, both $x + h$ and $y + h$ are less than $N$ and $T'[x + h] \ne T'[y + h]$. We write $\mathrm{lcp}(x, y)$ for $\mathrm{lcp}(T'_x, T'_y)$. A position is odd or even by its 0-based value. The proof is by induction on $N$; for $N \le 4$, line L1 is direct.

Lemma 1 (odd suffixes). After L4, $SA_o$ lists the odd positions in suffix order, and $LCP_o[k] = \mathrm{lcp}(SA_o[k-1], SA_o[k])$.

Proof. Let $m = \lfloor N/2 \rfloor$ be the number of odd positions, and for $0 \le i < m$ let $\pi_i = (T'[2i+1], T'[2i+2])$, with $T'[N] = 0$ as a pad. The pair $\pi_{m-1}$ contains $T'[N-1] = 0$ at its first or second place, and no other pair contains a 0, since $2i + 2 \le N - 2$ for $i < m - 1$. Line L2 sets $R[i]$ to the rank of $\pi_i$, so $R[i] < R[j]$ if and only if $\pi_i < \pi_j$, and $R[m-1]$ is unique. Read two symbols at a time, $T'_{2i+1}$ is $\pi_i \pi_{i+1} \cdots \pi_{m-1}$, followed by the pad. Two such sequences for $i \ne j$ differ at some pair before either ends, because the unique pair $\pi_{m-1}$ can only be matched by itself, at the same offset from the end, which would mean $i = j$. So comparing them pair by pair is comparing the suffixes of $R$ at $i$ and $j$ with the extra 0 of L3 never reached, and it is also comparing $T'_{2i+1}$ and $T'_{2j+1}$, since pairs compare as their two symbols. By induction ($|R| + 1 = m + 1 < N$ for $N > 4$), $SA_R$ is the suffix array of $R0$, whose rank 0 is the suffix $0$ at index $m$; dropping it and mapping $i$ to $2i + 1$ gives $SA_o$.

For the LCP, let $x = SA_o[k-1]$ and $y = SA_o[k]$, which are the suffixes of $R$ at ranks $k$ and $k + 1$ of $SA_R$, so $h = LCP_R[k+1]$ is the number of equal leading pairs, and by the argument above the first pair that differs comes no later than $\pi_{m-1}$ in either sequence. So $x + 2h$ and $y + 2h$ are the starts of the first pairs that differ, both less than $N$. If $T'[x + 2h] \ne T'[y + 2h]$, the lcp is $2h$. Otherwise the second symbols differ, and the lcp is $2h + 1$. $\square$

Lemma 2 (even suffixes). After L6, $SA_e$ lists the even positions in suffix order, and $LCP_e[k] = \mathrm{lcp}(SA_e[k-1], SA_e[k])$.

Proof. For an even $p < N - 1$, $T'_p = T'[p]\,T'_{p+1}$ with $p + 1$ odd and less than $N$. So for two such positions, $T'_p < T'_q$ if and only if $T'[p] < T'[q]$, or $T'[p] = T'[q]$ and $T'_{p+1} < T'_{q+1}$, that is, the rank of $p + 1$ in $SA_o$ is smaller (Lemma 1). If $N - 1$ is even, its suffix is the sentinel alone, the smallest suffix, and its key $(0, -1)$ is the smallest key. So sorting by the key of L5 sorts the even suffixes. For two adjacent even suffixes $a$ and $b$: if $T'[a] \ne T'[b]$, their lcp is 0; otherwise both symbols are nonzero, since the sentinel is unique, and $\mathrm{lcp}(a, b) = 1 + \mathrm{lcp}(a + 1, b + 1)$, which is the minimum of $LCP_o$ over the ranks after the smaller rank up to the larger rank by the LCP-RMQ lemma. $\square$

The trees and $M$. $\mathcal{T}_o$ and $\mathcal{T}_e$ are the compacted tries of the odd and the even suffixes; with distinct suffixes and no suffix a prefix of another, each suffix is a leaf. A point of a tree is a node or a place inside an edge; it spells a string, its path. The overmerge (L12 to L15) builds $M$ from pairs of points: the root of $M$ is paired with the two roots. At a node $v$ of $M$ paired with the points $s_o$ and $s_e$ (either may be missing), the edges out of $s_o$ and $s_e$ are grouped by first symbol. For each symbol $c$, a child $w$ of depth $d$ is made, where $d$ is the smaller depth of the targets of the edges with symbol $c$ (of one or both trees), and $w$ is paired with the points at depth $d$ on these edges. A leaf of a tree whose depth is $d$ makes $w$ a leaf of $M$ for that suffix. Let $P_o(w)$ and $P_e(w)$ be the paths of the points paired with $w$. By induction from the root:

• (a) the depth of $w$ in $M$ is $|P_o(w)|$ and $|P_e(w)|$, for each point that exists;
• (b) the odd leaves below $w$ in $M$ (with $w$ itself if it is an odd leaf) are exactly the odd leaves below the point of $w$ in $\mathcal{T}_o$, and in the same way for the even leaves;
• (c) the children of $w$ have different first symbols $c$, and $c$ is the true symbol at offset $\mathrm{depth}(w)$ of every suffix below that child;
• (d) every node of $\mathcal{T}_o$ is paired with some node of $M$, and so is every node of $\mathcal{T}_e$.

Point (d) holds because $d$ is never larger than the depth of either target, so the walk along an edge stops at its lower end. Each node of $M$ other than the root is at the lower end of an edge of one of the trees, so it is paired with a node of that tree, and each node of a tree is paired with only one node of $M$, since the walk goes down. So $M$ has at most $|\mathcal{T}_o| + |\mathcal{T}_e| = O(N)$ nodes, and the walk ends.

Lemma 3 (same parity). For two odd positions $x \ne x'$, $\mathrm{lcp}(x, x') = \mathrm{depth}_M(\mathrm{LCA}_M(x, x'))$. The same holds for two even positions.

Proof. Let $u$ be the LCA of $x$ and $x'$ in $\mathcal{T}_o$; its string depth is $\mathrm{lcp}(x, x')$. By (d), $u$ is paired with a node $w$ of $M$, and by (b) both leaves are below $w$. In $\mathcal{T}_o$, the two leaves are in different subtrees of $u$, whose edges have different first symbols, so by (c) they go to different children of $w$, or one of them is $w$. Hence $w$ is their LCA in $M$, and by (a) its depth is $\mathrm{lcp}(x, x')$. $\square$

Lemma 4 (different parity). For a node $v$ of $M$ with both points, let $\lambda(v) = \mathrm{lcp}(P_o(v), P_e(v))$, at most $\mathrm{depth}(v)$. For an odd $x$ and an even $y$ with $\mathrm{LCA}_M(x, y) = v$, $\mathrm{lcp}(x, y) = \lambda(v)$. Moreover $\lambda(v) = 0$ if and only if $v$ is the root.

Proof. By (b), $x$ starts with $P_o(v)$ and $y$ with $P_e(v)$. If $\lambda(v) < \mathrm{depth}(v)$, the two paths differ at offset $\lambda(v)$, so the suffixes do too, and $\mathrm{lcp}(x, y) = \lambda(v)$. If $P_o(v) = P_e(v)$, the suffixes share $\mathrm{depth}(v)$ symbols. Neither of them can be $v$ itself as a leaf: a leaf suffix ends with the sentinel at offset $\mathrm{depth}(v) - 1$, and the other suffix would hold the same sentinel at the same offset, so it would be the same suffix. So they go to different children of $v$, whose first symbols differ by (c), and $\mathrm{lcp}(x, y) = \mathrm{depth}(v) = \lambda(v)$. At the root, both paths are empty and $\lambda = 0$. At any other node, the first symbol of the path is the first symbol of the child of the root that holds $v$, which is a true symbol of both paths by (c), so $\lambda(v) \ge 1$. $\square$

Lemma 5 (d-links). Lines L16 to L18 return $\mathrm{lcp}(x, y)$ for $x$ and $y$ of different parity.

Proof. Let $v = \mathrm{LCA}_M(x, y)$. If $v$ is the root, the answer 0 is right by Lemma 4. Otherwise $\lambda(v) \ge 1$, so $T'[x] = T'[y]$, both symbols are nonzero, $x + 1$ and $y + 1$ are positions of different parity, and $\mathrm{lcp}(x, y) = 1 + \mathrm{lcp}(x + 1, y + 1)$. Each step of the loop goes to a pair one position further, so it ends at the root after at most $N$ steps, or earlier at a stored value. By induction along the chain from its end, each value computed is $\mathrm{lcp}$ of its pair, and by Lemma 4 that value is $\lambda(w)$ for the node $w$ where it is stored. So a stored value is right for every later pair with the same LCA. $\square$

Theorem 1 (correctness). FARACH returns the suffix array and the LCP array of $T'$.

Proof. By Lemmas 3 and 5, $\mathrm{LCP}(x, y) = \mathrm{lcp}(x, y)$ for any two positions. With $h = \mathrm{lcp}(x, y)$, $T'_x < T'_y$ if and only if $T'[x + h] < T'[y + h]$. So L9 merges two lists that are sorted by Lemmas 1 and 2 with a correct comparison, and the result lists all $N$ suffixes in order. L10 is correct by the same two lemmas. The recursion ends, since its input is shorter. $\square$

Theorem 2 (time). On an integer alphabet with $\sigma \le N^{O(1)}$, with radix sort and linear-time range minimum and LCA structures, FARACH takes $O(N)$ time in the worst case.

Proof. Without the recursive call: L2 is a radix sort of $m$ pairs with $O(1)$ passes; L4 is a scan; L5 is a stable counting sort by $T'[p]$ of the even positions taken in the order of $SA_o$; L6 is $O(N)$ range minimum queries after linear preprocessing; L7 is two stack scans; L8 is the overmerge, $O(1)$ work for each node of $M$ when the children of each point are grouped by first symbol with one global radix sort of all edges, and then linear LCA preprocessing. In L9 and L10 there are $O(N)$ LCP queries. Each query of a different parity costs $O(1)$ plus one loop step for each node whose value is stored for the first time, and each node of $M$ is stored at most once, so the total is $O(N)$. The recursive call is on $m + 1 \le N/2 + 1$ symbols, with names at most $m$. So $t(N) \le t(N/2 + 1) + cN$, which gives $t(N) = O(N)$, since the sizes form a geometric series. $\blacksquare$