后缀数组

字符串 · 后缀结构 · 倍增 O(n log²n)

把所有后缀排个序

一个长度 n 的串有 n 个后缀（从每个位置到末尾）。把它们按字典序排好，用一个数组 sa 记下顺序（sa[i] = 排名第 i 的后缀的起点下标），这就是后缀数组。别看它只是「排个序」，最长公共子串、不同子串计数、重复子串检测等一大批问题，都能站在它肩膀上快速解决——它是字符串的后缀结构基石。

前四页 KMP / Rabin-Karp / Boyer-Moore 是「找模式」、Manacher 是「找回文」，后缀数组则是「把后缀组织起来」——字符串处理的另一大支柱。

倍增：每轮把比较长度翻倍

直接对 n 个后缀排序，每次比较两个后缀最坏要扫 O(n) 个字符，总共 O(n² log n)，太慢。倍增法的巧思是：先按每个后缀的前 1 个字符排序、定一个 rank；然后用上一轮的 rank 拼出新关键字——后缀 i 的「前 2 位」可以表示成 (rank[i], rank[i+1])，「前 4 位」表示成 (rank[i], rank[i+2])……每轮比较长度翻倍，只需 O(log n) 轮、每轮排序 O(n log n)，合计 O(n log²n)。

关键在于不重复比较字符：这一轮的 rank 直接由上一轮拼出来，和 KMP 用部分匹配表、Manacher 用回文对称性一样，都是「复用已算结果」。

下面是 banana。点「下一步」逐轮看：每一轮先按关键字 (前 k 位 rank, 后 k 位 rank)重排（黄色高亮关键字列），再据相邻是否相等重编 rank（绿色高亮 rank 列），k 随之翻倍。两轮后所有 rank 互不相同，后缀数组定型 sa = [5,3,1,0,4,2]（a / ana / anana / banana / na / nana）。右侧代码随每一步同步高亮。

倍增长度 k = 1

起点后缀rank关键字 (前, 后)

1anana0(0, 2)

3ana0(0, 2)

5a0(0, ∞)

0banana1(1, 0)

2nana2(2, 0)

4na2(2, 0)

列出所有后缀，按首字符给每个后缀定初始 rank（a=0,b=1,n=2），据此排出初步顺序

1function suffixArray(s: string): number[] {
const n = s.length;
let rank = s.split('').map(c => c.charCodeAt(0)); // 初始 rank = 首字符
let sa = [...Array(n).keys()];
const key = (i: number, k: number): [number, number] =>
  [rank[i], i + k < n ? rank[i + k] : -1];
for (let k = 1; ; k <<= 1) {
  sa.sort((a, b) => {                             // 按 (前 k 位, 后 k 位) 排
    const ka = key(a, k), kb = key(b, k);
    return ka[0] - kb[0] || ka[1] - kb[1];
  });
  const nr = Array(n).fill(0);
  for (let x = 1; x < n; x++) {
    const kp = key(sa[x - 1], k), kq = key(sa[x], k);
    nr[sa[x]] = nr[sa[x - 1]] +                   // 重编 0 基 rank
      (kp[0] !== kq[0] || kp[1] !== kq[1] ? 1 : 0);
  }
  rank = nr;
  if (rank[sa[n - 1]] === n - 1) break;           // rank 全不同 → 收敛
}
return sa;
22}

原串banana

倍增长度 k1

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

1 / 6

后缀数组能做什么

不同子串计数：一个串的本质不同子串数 = 所有后缀长度之和 − 相邻后缀的 LCP 之和。
最长重复子串 / 最长公共子串：配合 height 数组（相邻后缀的最长公共前缀）一趟扫出。
模式匹配：后缀数组上二分，O(m log n) 判断模式是否出现。

本页只构造了后缀数组本身；再算一遍相邻后缀的最长公共前缀（height/LCP），上面这些应用就都水到渠成——那是后缀结构的下一步。再往深处走一层是后缀自动机（SAM）：把所有子串压进一个 O(n) 大小的自动机、在线逐字符构造，本质是「后缀们的合并版 Trie」——数不同子串、最长公共子串等问题在它上面是线性一遍。后缀数组好写好想适合多数场景，SAM 是学有余力时的下一座山。

算法可视化

后缀数组

把所有后缀排个序

倍增：每轮把比较长度翻倍

后缀数组能做什么