LCP Array Only

LCP Array Primer

This page teaches LCP itself: how long adjacent sorted suffixes match from the start, and why Kasai computes those lengths in linear time.

Reading Contract

This page answers one question: how adjacent sorted suffixes expose stable common-prefix lengths. After reading, you should be able to connect lcp[p], rank[i], h carry, and the Kasai scan.

Hand-drawn LCP and Kasai mental model: adjacent suffixes, rank, h carry, and LCP array — The LCP array stores lengths, not strings; Kasai works because the previous match length leaves a reusable h carry for the next start.

Read Only adjacent suffixes

Each LCP cell comes from neighboring rows after sorting, not from arbitrary substrings.

Core h is reusable slack

Kasai becomes linear because the next start can inherit h-1 before extending.

Check Read lcp[p]

You should know lcp[p] compares sa[p] with sa[p-1], and the value is a length.

Interval ms

Why

Adjacent suffixes

Aligned comparison

Kasai scan

i	rank	start	h	LCP

Knowledge links

What suffix arrays are LCP assumes suffixes are already sorted; suffix arrays do that sorting. Application: shortest unique subarray The application uses suffix-array neighbors and LCP lengths together.

C++

Core code

The key in Kasai is not the while loop alone; it is reusing h so the next start inherits h-1 before extending.

vector<int> buildLCP(string s, 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 h = 0;    for (int i = 0; i < n; i++) {        int p = rank[i];        if (p == 0) continue;        int j = sa[p - 1];        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;        lcp[p] = h;        if (h > 0) h--;    }    return lcp;}