LCP Array Only

LCP 数组入门

这一页只讲 LCP 本身：排好序的相邻后缀之间，开头到底连续相同了多长；以及 Kasai 为什么能线性扫出来。

阅读契约

本页只回答一个问题：排好序的相邻后缀之间，公共前缀长度如何被稳定地计算和读取。读完后，你应该能解释 lcp[p]、rank[i]、h carry 和 Kasai 扫描的关系。

LCP 和 Kasai 扫描心智模型手绘图：相邻后缀、rank、h carry 和 LCP array
LCP 数组不保存字符串，只保存“当前排序行和上一行像了多长”；Kasai 的关键是把上一轮公共前缀的余量带到下一轮。
读法 只比较相邻后缀

LCP 表里的每一格都来自排序后相邻两行，不是任意两段字符串。

核心 h 是可继承的余量

Kasai 线性化的关键是下一轮先继承 h-1，再继续向右扩展。

验收 能读 lcp[p]

读完应能说清 lcp[p] 比较 sa[p] 与 sa[p-1]，值是长度。

为什么

相邻后缀

字符对齐比较

Kasai 扫描

i rank 起点 h LCP

C++

核心代码

Kasai 的关键不是 while，而是 h 的复用：每次最多先继承 h-1，再继续向右扩展。

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;}