Proofs: Kasai's algorithm

Kasai's algorithm computes the LCP array in linear time full

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

Notation. $T = T[0 \ldots n-1]$, $n \ge 1$, and $T_p = T[p \ldots n-1]$ for $0 \le p \le n$, so $T_n$ is the empty string. The order $<$ on strings is the lexicographic order in which a proper prefix is smaller. $SA$ lists $T_0, \ldots, T_{n-1}$ in increasing order, and $RANK$ is its inverse. For $RANK[p] > 0$ let $\mathrm{pred}(p) = SA[RANK[p] - 1]$ and $\ell(p) = \mathrm{lcp}(T_{\mathrm{pred}(p)}, T_p)$. The claim is that after KASAI, $LCP[0] = 0$ and $LCP[RANK[p]] = \ell(p)$ for each $p$ with $RANK[p] > 0$.

Lemma 1 (sandwich). If $x \le y \le z$, then $\mathrm{lcp}(x, z) \le \mathrm{lcp}(x, y)$ and $\mathrm{lcp}(x, z) \le \mathrm{lcp}(y, z)$.

Proof. Let $k = \mathrm{lcp}(x, z)$ and $c = x[0 \ldots k-1] = z[0 \ldots k-1]$. Suppose that $y$ does not start with $c$, and let $j < k$ be the first index where $y$ and $c$ differ: either $|y| = j$, or $y[j] \ne c[j]$. If $|y| = j$ or $y[j] < c[j]$, then $y < x$, because $x$ starts with $c$ and so $x$ is longer than $j$ and agrees with $y$ before $j$. If $y[j] > c[j]$, then $y > z$ for the same reason. Both contradict $x \le y \le z$. So $y$ starts with $c$, and both inequalities follow. $\square$

Lemma 2 (drop one symbol). Let $RANK[p] > 0$ and $\ell(p) = h \ge 2$. Then $p + 1 < n$, $RANK[p+1] > 0$ and $\ell(p+1) \ge h - 1$.

Proof. Let $q = \mathrm{pred}(p)$. Both $T_q$ and $T_p$ have length at least $h \ge 2$ and $T[q] = T[p]$. Then $T_{q+1}$ and $T_{p+1}$ are $T_q$ and $T_p$ without their equal first symbol. They are nonempty, they share a prefix of length $h - 1$, and $T_{q+1} < T_{p+1}$, because removing an equal first symbol keeps the order. So $T_{p+1}$ is not the smallest suffix, which gives $RANK[p+1] > 0$. The suffix $T_{\mathrm{pred}(p+1)}$ is the largest suffix below $T_{p+1}$, so $T_{q+1} \le T_{\mathrm{pred}(p+1)} < T_{p+1}$. By Lemma 1, $\ell(p+1) = \mathrm{lcp}(T_{\mathrm{pred}(p+1)}, T_{p+1}) \ge \mathrm{lcp}(T_{q+1}, T_{p+1}) \ge h - 1$. $\square$

Theorem 1 (KASAI). Line L1 makes $RANK$ the inverse of $SA$. Then the loop of line L3 keeps this invariant at the start of round $p$:

(K) For each $p' < p$, the entry $LCP[RANK[p']]$ holds $0$ if $RANK[p'] = 0$ and $\ell(p')$ otherwise. Also $0 \le h$, and if $RANK[p] > 0$ then $h \le \ell(p)$. If $h \ge 1$, then $RANK[p] > 0$.

Initialization. At $p = 0$ no entry is claimed, and $h = 0$ by line L2.

Maintenance. If $RANK[p] = 0$, then by (K) $h = 0$, line L4 writes $LCP[0] = 0$ and keeps $h = 0$, and $h = 0$ satisfies (K) for $p + 1$. Otherwise line L5 sets $q = \mathrm{pred}(p)$. Since $h \le \ell(p)$, the first $h$ symbols of $T_p$ and $T_q$ are equal. Line L6 increases $h$ while the next symbols exist and are equal, so it stops exactly at $h = \ell(p)$. Line L7 writes the right value. Line L8 sets $h = \max(\ell(p) - 1, 0)$. If $\ell(p) \ge 2$, Lemma 2 gives $RANK[p+1] > 0$ and $h = \ell(p) - 1 \le \ell(p+1)$. If $\ell(p) \le 1$, then $h = 0$. In both cases (K) holds at the start of round $p + 1$.

Termination. The loop runs for $p = 0, \ldots, n-1$ and stops. Each inner loop stops, because $h$ grows by 1 in each step and is bounded by $n - p$. At the end, (K) with $p = n$ covers every position, and $RANK$ is a bijection onto the indices $0, \ldots, n-1$, so every entry of $LCP$ is right. $\square$

Theorem 2 (time). Line L6 increases $h$ at most $2n$ times in total, so KASAI takes $\Theta(n)$ time.

Proof. The value $h$ is at most $n$ at all times. It decreases only at line L8, by 1, at most once in each of the $n$ rounds. Line L4 does not change it, because $h = 0$ there by (K). So the number of increases is at most the final value plus the number of decreases, which is at most $n + n$. Each round does $O(1)$ other work, and the failed test that ends line L6 costs $O(1)$ for each round. Line L1 takes $\Theta(n)$ time. $\blacksquare$