LCP Array, in depth: Kasai linear-time construction, the proof, a full banana trace, the PLCP variant and the string problems it solves

Definitions

Let s be a string of length n, and write s[i:] for the suffix that starts at position i. The suffix array SA is the permutation of 0..n-1 that lists suffix start positions in lexicographic order, so s[SA[0]:] < s[SA[1]:] < .... Its inverse, rank, maps a text position to its row in the sorted order: rank[SA[i]] = i.

The LCP array is defined on rows: LCP[i] is the length of the longest common prefix of the suffixes in rows i - 1 and i. LCP[0] has no predecessor; this page sets it to 0, while some libraries use -1 or leave it undefined, which is the first thing to check when you mix code from different sources. A closely related array, the permuted LCP or PLCP, is indexed by text position instead: PLCP[SA[i]] = LCP[i]. Kasai's algorithm is easiest to understand through PLCP, because it computes the values in text order.

Worked example: banana

Take s = banana, n = 6. Its six suffixes sorted are a (position 5), ana (3), anana (1), banana (0), na (4) and nana (2). So SA = [5, 3, 1, 0, 4, 2] and rank = [3, 2, 5, 1, 4, 0]. Comparing each row with the one above gives LCP = [0, 1, 3, 0, 0, 2]: ana shares a with a, anana shares ana with ana, banana shares nothing with anana, and so on.

Two results drop out immediately. The maximum LCP value is 3, at the row for anana, so the longest substring that occurs at least twice is ana. And the number of distinct non-empty substrings is the number of all substrings, 6 x 7 / 2 = 21, minus the sum of the LCP array, 6, which gives 15. Each suffix contributes its length in prefixes, and the LCP with its predecessor counts how many of those prefixes were already counted.

Why the naive method is quadratic, and the lemma that fixes it

The obvious algorithm compares each row with its predecessor character by character. For text with long repeats, such as aaaa...a, adjacent suffixes share almost everything, and the total comparison count is about n squared over 2.

Kasai's insight is a relation between consecutive text positions. Suppose suffix s[i:] has a common prefix of length h > 0 with its sorted predecessor s[j:]. Drop the first character of both. Then s[i+1:] and s[j+1:] share h - 1 characters, and because s[j:] sorted before s[i:] and they agreed on the first character, s[j+1:] still sorts before s[i+1:]. The sorted predecessor of s[i+1:] lies between them in the order, so it shares at least h - 1 characters with s[i+1:] too. In PLCP terms: PLCP[i+1] >= PLCP[i] - 1.

So if you process suffixes in text order, you never have to start matching from zero: start at h - 1 and extend. The counter h never exceeds n and decreases by at most one per step, so over the whole run it can increase at most about 2n times. Each increase is one successful character comparison and each step has at most one failing comparison, so the total work is O(n) once the rank array is built.

The algorithm in code

The implementation is short. Build rank by inverting SA, then walk i from 0 to n - 1 in text order, find the predecessor row, extend h and write the result at the suffix's row.

def lcp_kasai(s, sa):
    """LCP[i] = longest common prefix of suffixes sa[i-1] and sa[i]; LCP[0] = 0."""
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp = [0] * n
    h = 0
    for i in range(n):                 # suffixes in text order
        r = rank[i]
        if r == 0:                     # no predecessor in sorted order
            h = 0
            continue
        j = sa[r - 1]                  # the suffix just before s[i:] in sorted order
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[r] = h
        if h > 0:
            h -= 1                     # the lemma: next suffix keeps at least h - 1
    return lcp

The C++ version is a line-for-line translation; its running time is dominated by cache misses on the random accesses to sa[r - 1] and the text.

std::vector<int> lcp_kasai(const std::string& s, const std::vector<int>& sa) {
    const int n = static_cast<int>(s.size());
    std::vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; ++i) {
        if (rank[i] == 0) { 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;
}

Tracing banana by hand

Follow the loop with SA = [5, 3, 1, 0, 4, 2] and rank = [3, 2, 5, 1, 4, 0]. At i = 0, the row is 3 and its predecessor is position 1: banana against anana fails at once, so LCP[3] = 0 and h stays 0. At i = 1, the row is 2 and its predecessor is position 3: anana against ana matches three characters before ana runs out, so LCP[2] = 3 and h becomes 2.

At i = 2, the row is 5 and its predecessor is position 4. The lemma says nana and na share at least 2 characters, and indeed matching starts at offset 2 and stops immediately because na has ended, so LCP[5] = 2 with no comparisons wasted on the shared part. h becomes 1. At i = 3, row 1, predecessor position 5: start at 1, a is exhausted, LCP[1] = 1, h becomes 0. At i = 4, row 4, predecessor position 0: na against banana fails, LCP[4] = 0. At i = 5 the row is 0, so there is no predecessor. The result matches the table above.

Building the suffix array first

Kasai needs a suffix array as input. For learning and for inputs up to about a hundred thousand characters in Python, prefix doubling is enough: sort suffixes by their first k characters using the ranks from the previous round as a pair key, and double k until every rank is distinct.

def suffix_array(s):
    """Prefix doubling: O(n log^2 n) with Python's sort. Fine up to ~10^5 characters."""
    n = len(s)
    if n == 0:
        return []
    sa = list(range(n))
    rank = [ord(ch) for ch in s]
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        new = [0] * n
        for t in range(1, n):
            new[sa[t]] = new[sa[t - 1]] + (key(sa[t - 1]) < key(sa[t]))
        rank = new
        if rank[sa[-1]] == n - 1:      # all ranks distinct: fully sorted
            return sa
        k *= 2

Production code uses a linear-time construction such as SA-IS, or a radix-sorted doubling in O(n log n), via a library such as libsais or divsufsort in C and C++.

What the LCP array is for

Most uses rest on one fact: for rows p < q, the longest common prefix of the suffixes in those rows is the minimum of LCP[p+1..q]. Suffixes sharing a prefix are contiguous in sorted order, so the common prefix of the two ends of a range can be no longer than the weakest adjacent link. Preprocess the LCP array for range minimum queries with a sparse table in O(n log n), or with a Cartesian tree in O(n), and the LCP of any two suffixes is an O(1) query. A segment tree works when you need O(log n) queries with updates.

def distinct_substrings(s):
    sa = suffix_array(s)
    return len(s) * (len(s) + 1) // 2 - sum(lcp_kasai(s, sa))

def longest_repeated(s):
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    i = max(range(len(s)), key=lambda t: lcp[t], default=0)
    return s[sa[i]:sa[i] + lcp[i]] if s else ""

def longest_common_substring(a, b, sep="\x00"):
    assert sep not in a and sep not in b
    s = a + sep + b
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    best, at = 0, 0
    for i in range(1, len(s)):
        if (sa[i - 1] < len(a)) != (sa[i] < len(a)) and lcp[i] > best:
            best, at = lcp[i], sa[i]
    return s[at:at + best]

def brute_lcp(s, sa):                  # the definition, for tests
    out = [0]
    for i in range(1, len(sa)):
        x, y, h = s[sa[i - 1]:], s[sa[i]:], 0
        while h < min(len(x), len(y)) and x[h] == y[h]:
            h += 1
        out.append(h)
    return out

The longest common substring of two strings uses a separator that occurs in neither and sorts below every real character, then looks only at adjacent rows whose suffixes come from different inputs. Substring search on a suffix array is a binary search costing O(m log n) for a pattern of length m; keeping track of LCP values during the search reduces it to O(m + log n), as in Manber and Myers' original suffix array paper.

Memory, and the PLCP variant

With 32-bit integers, the text plus SA, rank and LCP take about 13 bytes per character, and inputs over 2 billion characters need 64-bit indices, which nearly doubles that. The Phi algorithm of Kärkkäinen, Manzini and Puglisi computes PLCP in text order using one auxiliary array of predecessors, then permutes it into LCP. Its inner loop reads the text sequentially at i + h, and implementations can reuse buffers, which makes it a common choice for large inputs.

def lcp_phi(s, sa):
    """Kärkkäinen-Manzini-Puglisi: compute PLCP in text order, then permute."""
    n = len(s)
    phi = [-1] * n
    for i in range(1, n):
        phi[sa[i]] = sa[i - 1]         # predecessor of each suffix, indexed by text position
    plcp = [0] * n
    h = 0
    for i in range(n):
        j = phi[i]
        if j == -1:
            h = 0
            continue
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        plcp[i] = h
        h = max(h - 1, 0)
    return [plcp[p] for p in sa]       # LCP[i] = PLCP[SA[i]]

Failure modes and how to test

• Sentinel confusion. Some code appends a terminator such as $ and some does not; mixing a suffix array from one convention with LCP code from another shifts every row. Decide once and assert len(sa) == len(s).
• LCP[0] conventions. 0, -1 or undefined. Range minimum code that includes row 0 by mistake returns 0 or -1 for every range.
• Overflow. The number of substrings, n times (n + 1) / 2, overflows 32 bits once n exceeds about 92,000. Use 64-bit counters.
• Separator collisions. If the separator can occur in the input, longest common substring results silently cross the boundary.
• Bytes versus characters. Building on UTF-8 bytes gives substrings that can split a code point; decide which unit you index and decode results accordingly.

The cheapest strong test is differential: generate many random short strings over a two- or three-letter alphabet, where repeats are frequent, build the suffix array by sorting the suffixes directly, and compare lcp_kasai with brute_lcp. Add all-equal strings and strings with no repeats as edge cases.

Trade-offs against other tools

A suffix tree answers the same questions with more flexibility but uses many times more memory. A suffix automaton is compact and excellent for counting and for longest common substring of two strings, but less natural for ordered queries. Polynomial hashing with binary search finds the longest repeat in O(n log n) with a small risk of collision and almost no memory. For single-pattern matching, KMP is simpler; for many short keys, a trie is the better index. Choose the suffix array with LCP when you need many different substring queries over one large, static text.

What to do next

1. Implement suffix_array and lcp_kasai from this page and trace banana by hand against the output.
2. Write the differential test against the brute-force definition and run it on thousands of random strings.
3. Use the arrays to count distinct substrings and find the longest repeat in a real file such as a log.
4. Add a sparse table over the LCP array and answer LCP queries between arbitrary suffixes.
5. For large inputs, switch construction to a library SA-IS implementation and benchmark Kasai against the Phi variant.