【为什么需要后缀数组】

先看一个题：给一个长度 10^5 的字符串，找出其中最长的重复子串（至少出现两次，可重叠）。暴力枚举所有子串再判断，复杂度直接爆炸。

这类问题的根本是后缀。一个字符串的所有后缀，包含了所有子串的信息。比如 banana 的后缀有 banana, anana, nana, ana, na, a。如果我们把这些后缀按字典序排个队，许多公共前缀凑在一起，找重复子串就变成了找相邻后缀的公共前缀。后缀数组就是干这件事的——给所有后缀排个序。

---

【后缀数组速通：sa, rank, height 三兄弟】

• sa[i]：排名第 i 的后缀是哪个？存的是这个后缀的起始位置（下标）。

• rank[i]：起始位置 i 的后缀排第几？和 sa 互为反函数，rank[sa[i]] = i。

• height[i]：排名第 i 的后缀和排名第 i-1 的后缀的 最长公共前缀 (LCP) 长度。

倍增法构造简述：不用深究基数排序细节，记住逻辑就行：
先给所有后缀的第一个字符排名；然后每次把长度翻倍——用 (当前排名, 后一半的排名) 作为二元组重新排序，相当于把每个后缀的前 2^k 个字符排好。排序用桶排优化，总复杂度 O(n log n)。

构造完后，我们就有了 sa 和 rank。height 数组可以通过一个性质 O(n) 求出：height[rank[i]] ≥ height[rank[i-1]] - 1，相当于一个指针只减不增。

---

【height 的妙用：任意两个后缀的 LCP】

想求位置 i 和 j 的两个后缀的 LCP？不直接求，而是看它们在 sa 中的排名。
结论：LCP(i, j) = min{ height[k] }，k 从 rank[i]+1 到 rank[j]（假设 rank[i] < rank[j]）。
也就是说，两个后缀的公共前缀长度，等于它们排名之间所有相邻 LCP 的最小值。这就转化成了 RMQ 问题，可以用 ST 表 O(1) 查询。任意两个后缀的 LCP 都能秒出。

---

【后缀自动机入门：像拼乐高一样构建】

后缀自动机 (SAM) 是接受一个字符串所有后缀的最小确定性有限自动机。听起来吓人，其实可以这么想：

你要拼一个能识别所有后缀的“乐高城堡”。初始只有一间空房（根节点），每读入一个字符，就像在城堡上接一块新乐高。这块乐高可能恰好接在现有某个房间后，也可能要新建房间，甚至把之前的某些房间拆开、加一条新通道。

每个房间有三个关键信息：

• len：这个房间代表的最长子串长度。

• link：失配后去的房间，指向另一个包含相同后缀但更短的房间。

• next[26]：读完一个字符后去哪个房间。

link 特别像 KMP 的失配指针，它把所有房间串成一棵“后缀链接树”，这棵树就是后面统计出现次数的关键。

构建过程是在线的，每次加一个字符，可能需要 1 到 2 个新节点，均摊 O(n)。

---

【模板代码】

后缀数组 (SA) 倍增模板：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int sa[N], rk[N], oldrk[N << 1], id[N], cnt[N], height[N];
int n;

void build_sa() {
    int m = 127; // 字符集大小
    // 第一轮按单个字符基数排序
    for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
    for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
    // 倍增
    for (int w = 1; w < n; w <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++) id[i] = sa[i];
        for (int i = 1; i <= n; i++) cnt[rk[id[i] + w]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[id[i] + w]]--] = id[i];
        // 同理排前半截，代码略，完整模板见网盘
        // 更新 rk
    }
    // 计算 height
    for (int i = 1, k = 0; i <= n; i++) {
        if (k) k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;
        height[rk[i]] = k;
    }
}

后缀自动机 (SAM) 模板：

struct SAM {
    int len, link, next[26];
} st[N << 1];
int sz, last;

void sam_init() {
    st[0].len = 0; st[0].link = -1;
    sz = 1; last = 0;
}

void sam_extend(int c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    while (p != -1 && !st[p].next[c]) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].link = st[q].link;
            memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

---

【经典例题】

1. 最长公共子串（用 SA）

• 题目链接：SP1811 LCS - Longest Common Substring

• 题意：给两个字符串，求它们的最长公共子串。

• 思路：把两个串拼成 S + '#' + T，求 SA 和 height。答案是最大的 height，且对应的两个后缀分别来自 S 和 T。因为 height 本来就是相邻排名后缀的 LCP，遍历一遍即可。

• 核心代码：

  int ans = 0;
  for (int i = 2; i <= n; i++) {
      // 判断两个后缀是否分属不同串
      if ((sa[i-1] <= lenS && sa[i] > lenS+1) ||
          (sa[i-1] > lenS+1 && sa[i] <= lenS))
          ans = max(ans, height[i]);
  }
  cout << ans << endl;

2. 本质不同子串数量（用 SA 或 SAM）

• 题目链接：洛谷 P2408 不同子串个数

• 题意：给一个字符串，求本质不同的子串个数。

• SA 思路：子串总数是 n*(n+1)/2，重复的子串就是所有相邻后缀的公共前缀。所以答案是总数减去所有 height 的和。ans = n*(n+1)/2 - sum(height[i])。

• SAM 思路：SAM 上每个节点 u 代表一些子串，长度连续，范围为 (len[link[u]], len[u]]，个数就是 len[u] - len[link[u]]。累加所有节点的这个差值就得到答案。

3. 子串出现次数（SAM 模板题）

• 题目链接：洛谷 P3804 【模板】后缀自动机 (SAM)

• 题意：求所有长度大于 1 的子串中，出现次数乘长度的最大值。

• 思路：建 SAM 后，每个非克隆节点初始出现次数为 1（代表前缀的那个节点）。然后在后缀链接树上按 len 从大到小累加，得到 endpos 集合大小即出现次数。最后遍历所有节点，用 cnt[u] * len[u] 更新答案。

• 核心代码：

  for (int i = 1; i < sz; i++) cnt[st[i].len]++;
  for (int i = 1; i <= n; i++) cnt[i] += cnt[i-1];
  for (int i = 1; i < sz; i++) id[cnt[st[i].len]--] = i;
  // 按 len 降序累加出现次数
  for (int i = sz-1; i >= 1; i--) {
      int v = id[i];
      endpos[st[v].link] += endpos[v];
  }
  long long ans = 0;
  for (int i = 1; i < sz; i++) {
      if (endpos[i] > 1)
          ans = max(ans, 1LL * endpos[i] * st[i].len);
  }

---

【怎么选：SA vs SAM】

角度	后缀数组 (SA)	后缀自动机 (SAM)
思路	简单暴力：排序后缀	精巧 DFA，理论最优
编码量	较长（倍增+基数排序）	适中（约 30 行）
时间复杂度	O(n log n)	O(n) 在线
空间	一般 O(n)	O(n *	Σ	) 或 O(n) 用 map
适用场景	LCP 问题、字典序相关	子串计数、匹配、本质不同子串
扩展性	结合 ST 表可以求任意 LCP	可在 link 树上 DP，功能更强

口语化总结：

• 追求省事、处理字典序，比如求第 k 小子串，用 SA 顺位直接。

• 追求极致效率和在线操作，或者要在自动机上游走匹配，用 SAM 更灵巧。

• 比赛里如果字符集不大，SAM 的代码其实比 SA 还好背。

---

这篇文章信息量较大，包含了 SA 和 SAM 两大块。如果打算分两期发，可以上期讲 SA 和 height，下期专攻 SAM，例题也对应拆分，读者更容易消化。