LCP / height 数组

字符串 · 后缀结构 · Kasai O(n)

后缀数组的黄金搭档

后缀数组把所有后缀排好了序，但只有顺序还不够——很多问题要知道相邻两个后缀有多「像」。LCP 数组（又叫 height）就补上这一环：lcp[i] = 排序后第 i-1 个和第 i 个后缀的最长公共前缀（Longest Common Prefix）长度。有了 sa + lcp，一大批字符串问题一趟就能算出来。

Kasai：h 只减 1 的妙处

直接对每对相邻后缀逐字符比较是 O(n²)。Kasai 算法做到 O(n)，靠一个漂亮的单调性：按后缀在原串中的起点 i = 0,1,2… 的顺序处理（不是按排序顺序！），维护当前的公共前缀长度 h。关键观察——如果后缀 i 和它的排序前驱有 h 个公共字符，那么去掉首字符的后缀 i+1，和它自己的排序前驱至少有 h−1 个公共字符。

所以每处理一个后缀，h 至多减 1，之后只增不重比——整个过程 h 的总变化是 O(n)，字符不重复比较。代价是：LCP 列会按原始下标顺序、跳着填（而非从上到下），这正是 Kasai 聪明的地方。

下面复用 banana 的后缀数组（sa=[5,3,1,0,4,2]）。点「下一步」逐步看：当前处理的后缀行琥珀高亮、它的排序前驱行蓝高亮，LCP 列被填上；留意 lcp 不是从上往下顺序填的（Kasai 按原始下标跳）。走到底，lcp = [0,1,3,0,0,2]——最长重复子串就是 max(lcp)=3（"ana"）。右侧代码随每一步同步高亮。

LCP：相邻后缀最长公共前缀（Kasai）

起点后缀rankLCP↑

5a0-

3ana1

1anana2

0banana3

4na4

2nana5

后缀已按字典序排好（sa）；现在自上而下算每对相邻后缀的最长公共前缀 LCP，用 Kasai 只需 O(n)

1function kasai(s: string, sa: number[]): number[] {
const n = s.length;
const rank = new Array(n);
for (let i = 0; i < n; i++) rank[sa[i]] = i; // sa 的逆
const lcp = new Array(n).fill(0);
let h = 0;
for (let i = 0; i < n; i++) {          // 按原始下标 i 顺序处理
  if (rank[i] > 0) {
    const j = sa[rank[i] - 1];         // 排序前驱后缀
    while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++; // h 只增
    lcp[rank[i]] = h;                  // 填 LCP
    if (h > 0) h--;                    // 去首字符：h 至多减 1
  } else {
    h = 0;                             // rank 0：无前驱
  }
}
return lcp;
18}

原串banana

sa[5,3,1,0,4,2]

当前后缀 i-

1 / 8

sa + lcp 能一趟解决什么

最长重复子串：max(lcp)——出现两次以上的最长子串。
本质不同子串数：n(n+1)/2 − Σlcp（所有子串数减去重复计入的公共前缀）。banana → 21 − 6 = 15。
最长公共子串（两个串）：拼接后建 sa + lcp，找分属两串的相邻后缀里最大的 lcp。

至此字符串大类六页，后缀结构从构造（后缀数组）走到了应用（LCP）——它们和三种匹配、Manacher 一起，共同的主题依然是用预处理和已算结果，把暴力比较省下来。

算法可视化

LCP / height 数组

后缀数组的黄金搭档

Kasai：h 只减 1 的妙处

sa + lcp 能一趟解决什么