Kasai Algorithm

Purpose: Given a string and its suffix array, build the LCP array — lcp[i] = length of the longest common prefix of sa[i] and sa[i-1] — in $O(n)$ time.

Algorithm

1. Build rank[], the inverse of the suffix array: rank[sa[i]] = i.
2. Walk the suffixes in string order (i = 0 … n-1), not suffix-array order, maintaining a running value $k$.
3. For suffix $i$ at rank $r=\text{rank}[i]$: if $r=0$ there is no predecessor, so set $k=0$ and continue.
4. Otherwise let $j=\text{sa}[r-1]$ and extend the match character by character from the current $k$: while s[i+k] == s[j+k], increment $k$.
5. Store lcp[r] = k, then decrement $k$ (but not below 0) before moving to suffix $i+1$.

Code

vector<int> kasai(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
 
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) { k = 0; continue; }
        int j = sa[rank[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rank[i]] = k;
        if (k) k--;
    }
    return lcp;
}

Paradigm

Amortized two-pointer. Nothing clever happens per suffix; the magic is entirely in the accounting.

Complexity

• Time: $O(n)$
• Space: $O(n)$ for rank and lcp

Proof of Correctness

The key lemma is:

$\mathrm{lcp}(\text{rank}[i])\ge \mathrm{lcp}(\text{rank}[i-1])-1.$

Why: suppose suffix $i-1$ shares a prefix of length $k$ with its suffix-array predecessor $j-1$. Then suffix $i$ (which is suffix $i-1$ with the first character removed) shares a prefix of length $k-1$ with suffix $j$. Suffix $j$ sits somewhere before suffix $i$ in sorted order, and the LCP with the immediate predecessor is at least the LCP with any earlier suffix (LCP values along the suffix array are the minimum over the intervening range). Hence lcp[rank[i]] ≥ k - 1.

That lemma is exactly what licenses starting the character comparison loop at $k-1$ instead of $0$. Now count: $k$ increases by 1 per successful character comparison and decreases by at most 1 per outer iteration. There are $n$ outer iterations, so $k$ decreases at most $n$ times total; since $k\le n$ always, it can increase at most $2n$ times. Total comparisons $O(n)$. ∎

Variants / Use Cases

• Number of distinct substrings — $\frac{n(n+1)}{2}-\sum \text{lcp}[i]$
• Longest repeated substring — $\max \text{lcp}[i]$
• Longest common substring of two strings — concatenate with a separator, take the max lcp between suffixes from different halves
• LCP of arbitrary suffixes — a sparse table RMQ over the LCP array answers $\mathrm{lcp}(i,j)$ in $O(1)$
• Suffix array + LCP as a poor man’s suffix tree — most suffix-tree problems have an SA+LCP formulation
• SA-IS — the linear-time way to get the suffix array Kasai consumes