Kasai's O(N) LCP Array Algorithm & Counting Distinct Substrings via SA + LCP

1. Kasai's Theorem: Why $\text{LCP}$ Drops by at Most $1$ in Text Order

Let $\text{rank}[i] \in [0, N-1]$ be the inverse permutation of $\text{SA}$, so $\text{SA}[\text{rank}[i]] = i$. Suppose suffix $i$ at rank $r = \text{rank}[i] < N - 1$ shares a longest common prefix of length $h > 0$ with the next suffix in sorted order, $j = \text{SA}[r + 1]$:

Now delete the first character $S[i] = S[j]$ from both suffixes! We obtain suffix $S[i+1..]$ and suffix $S[j+1..]$:

1. Because $S[i..]$ is lexicographically smaller than $S[j..]$ and their first characters are identical ($h \ge 1$), suffix $S[i+1..]$ MUST still be lexicographically smaller than $S[j+1..]$, so $\text{rank}[i+1] < \text{rank}[j+1]$.
2. Moreover, $S[i+1..]$ and $S[j+1..]$ share a common prefix of length exactly $h - 1$: $S[i+1..i+h-1] = S[j+1..j+h-1]$.
3. By the LCP Range Minimum Property, any suffix lying lexicographically between $\text{rank}[i+1]$ and $\text{rank}[j+1]$ in $\text{SA}$ (specifically the immediate neighbor $\text{SA}[\text{rank}[i+1] + 1]$) must ALSO share a common prefix of length at least $h - 1$ with $S[i+1..]$!

Therefore, when moving from text index $i$ to $i + 1$, we simply set if (h > 0) --h; and start comparing characters from offset $h$ onward!

2. Three Classic Applications of $\text{SA} + \text{LCP}$

• Arbitrary Suffix LCP via RMQ: For any two suffixes at ranks $r_1 < r_2$ in $\text{SA}$, the length of their longest common prefix is the minimum of adjacent LCPs between them: $$\text{LCP}(\text{SA}[r_1],\; \text{SA}[r_2]) = \min_{r_1 \le k < r_2} \text{lcp}[k]$$ Building a Sparse Table over $\text{lcp}[0..N-2]$ answers $\text{LCP}(i, j)$ for any two text positions in $O(1)$ time!
• Counting Distinct Substrings in $O(N)$: Every substring of $S$ is a prefix of some suffix $\text{SA}[r]$. Suffix $\text{SA}[r]$ has length $N - \text{SA}[r]$, so it contributes $N - \text{SA}[r]$ prefixes in total, of which $\text{lcp}[r-1]$ were already counted as prefixes of the preceding suffix $\text{SA}[r-1]$. Summing the newly introduced prefixes across all ranks gives: $$\text{Distinct Substrings}(S) = \frac{N(N + 1)}{2} - \sum_{r=0}^{N-2} \text{lcp}[r]$$
• Longest Repeated Substring: The maximum value $\max_{0 \le r < N-1} \text{lcp}[r]$ is the exact length of the longest substring that appears at least twice in $S$.

3. Visual Trace: Kasai LCP & Distinct Substrings on $S = \texttt{"banana"}$

4. Production Implementation: Kasai's $O(N)$ LCP & Distinct Substring Counter

#include <cstdint>
#include <numeric>
#include <string_view>
#include <vector>

// Kasai's O(N) Algorithm: returns lcp[0..N-2] where lcp[r] = LCP(SA[r], SA[r+1])
std::vector<int> build_lcp_kasai(std::string_view s, const std::vector<int>& sa) {
    const int n = static_cast<int>(s.size());
    if (n <= 1) return {};

    std::vector<int> rank(n, 0);
    for (int r = 0; r < n; ++r) {
        rank[sa[r]] = r;
    }

    std::vector<int> lcp(n - 1, 0);
    int h = 0;
    for (int i = 0; i < n; ++i) {
        if (rank[i] == n - 1) {
            h = 0;
            continue;
        }
        int j = sa[rank[i] + 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
            ++h;
        }
        lcp[rank[i]] = h;
        if (h > 0) --h;
    }
    return lcp;
}

// Counts total distinct non-empty substrings of S in O(N) after SA + LCP construction
int64_t count_distinct_substrings(int64_t n, const std::vector<int>& lcp) {
    int64_t total_substrings = n * (n + 1) / 2;
    int64_t duplicate_prefixes = std::accumulate(lcp.begin(), lcp.end(), int64_t{0});
    return total_substrings - duplicate_prefixes;
}