1. 从一道经典题看透子串计数的两条路
如果你刷过字符串专题的题单，大概率会在某个位置撞上“不同子串个数”这道题。题目本身一句话就能说清：给一个长度为 n 的字符串，问它一共有多少个本质不同的子串。但真正有意思的地方在于，这道题几乎是字符串算法学习路上的一个分水岭——它同时能用后缀数组（SA）加 LCP 做，也能用后缀自动机（SAM）做，而且两条路的思维方式截然不同。
我第一次做这道题的时候，脑子里第一反应是暴力枚举所有子串塞进哈希表去重。n 小的时候这招确实能过，但 n 一旦上到 10^5 级别，O(n²) 个子串直接爆炸，内存和时间都扛不住。后来才明白，这类计数问题的核心不是“枚举”，而是“利用字符串的结构去避免重复计数”。SA 和 SAM 恰好是两种不同的结构视角：SA 从后缀的排序关系切入，SAM 从子串的等价类切入。
这篇文章我打算把两条路都完整走一遍，不只是贴代码，而是把每一步为什么这么算、边界怎么处理、容易踩什么坑都讲清楚。适合已经了解后缀数组或后缀自动机基本概念、但还没真正把“不同子串计数”这个模型吃透的读者。如果你连基数排序都还没写过，建议先把 SA 的构造啃下来再回来看，不然中间会卡壳。
先说结论，方便你带着目标读：SA 做法的答案是所有后缀长度之和减去相邻后缀 LCP 之和；SAM 做法的答案是每个状态的 len 减去其 link 指向状态的 len，再全部求和。两个公式都极其简洁，但简洁背后各有各的道理，下面逐个拆。
2. 后缀数组路线：用排序消掉重复的那部分
2.1 为什么“总长度减 LCP”就是答案
先建立一个直觉。一个长度为 n 的字符串，它的所有后缀一共有 n 个，第 i 个后缀的长度是 n - i + 1（假设下标从 1 开始）。如果把每个后缀的所有前缀都列出来，那这些前缀的集合恰好就是原串的所有子串——因为任何一个子串，都是某个后缀的前缀。所以“所有后缀长度之和”其实等于“所有子串按出现位置计数的总数”，这里面包含了大量重复。
关键在于怎么去重。后缀数组把所有后缀按字典序排好了序，这个排序有一个非常重要的性质：任意两个后缀的最长公共前缀（LCP），等于它们在排序后相邻区间内所有相邻 LCP 的最小值。换句话说，排序之后，重复的子串只会集中出现在相邻后缀之间。
具体来说，对于排序后第 i 个后缀，它贡献的“新子串”数量是它的长度减去它与前一个后缀的 LCP。为什么？因为它的前 LCP 个前缀，已经作为前一个后缀的前缀出现过了，只有从第 LCP+1 个字符开始往后的那些前缀才是全新的。把所有后缀的这个“新增量”加起来，就得到了本质不同子串的总数。
用公式写就是：
answer = Σ (n - sa[i] + 1) - Σ lcp[i]其中 sa[i] 是排名为 i 的后缀的起始位置，lcp[i] 是排名 i 和 i-1 的后缀的最长公共前缀（lcp[1] 通常定义为 0）。
2.2 手推一个小例子验证公式
光看公式容易飘，拿个具体串走一遍。设 s = “ababa”，n = 5。
所有后缀：
- 位置1：ababa
- 位置2：baba
- 位置3：aba
- 位置4：ba
- 位置5：a
按字典序排序后：
- a（位置5）
- aba（位置3）
- ababa（位置1）
- ba（位置4）
- baba（位置2）
后缀长度之和：1 + 3 + 5 + 2 + 4 = 15。
相邻 LCP：
- lcp(1,2)：a 和 aba 的公共前缀是 “a”，长度 1
- lcp(2,3)：aba 和 ababa 的公共前缀是 “aba”，长度 3
- lcp(3,4)：ababa 和 ba 的公共前缀为空，长度 0
- lcp(4,5)：ba 和 baba 的公共前缀是 “ba”，长度 2
LCP 之和：1 + 3 + 0 + 2 = 6。
答案：15 - 6 = 9。
手动枚举验证一下 “ababa” 的不同子串：a, b, ab, ba, aba, bab, abab, baba, ababa，正好 9 个。公式成立。
这个例子里有个细节值得注意：lcp 数组是相对于排序后的相邻后缀定义的，不是原始位置相邻。很多人第一次写的时候会把原始相邻位置的后缀拿去做 LCP，结果怎么算都不对。排序这一步是去重的核心，不能省。
2.3 后缀数组与 height 数组的构造要点
要把上面的公式落地，需要两样东西：sa 数组和 height 数组（height[i] 就是上面说的 lcp[i]）。sa 的构造方法有倍增法和 SA-IS 线性法，竞赛里倍增法更常写，因为好写好调，O(n log n) 对大多数题目够用。
倍增法的核心思路是：先按第一个字符排序，然后按前 2 个字符、前 4 个字符……逐步扩大比较的长度，每一轮利用上一轮的排名做基数排序。这里有个容易忽略的点——基数排序的两趟顺序不能反。第二关键字要先排，第一关键字后排，因为基数排序是从低位到高位稳定的。我见过不少人把两趟写反，小数据看不出来，大数据直接错。
height 数组的构造用的是那个著名的性质：height[rank[i]] >= height[rank[i-1]] - 1。利用这个性质可以把求 height 的复杂度从 O(n²) 降到 O(n)。实现的时候用一个指针 k 维护当前 LCP 长度，每次从上一个位置减一开始，然后暴力往后匹配。虽然内层看着像暴力，但 k 总共只会增加 n 次，所以整体是线性的。
下面给一份可复现的倍增法 SA + height 模板（C++）：
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int sa[MAXN], rk[MAXN], oldrk[MAXN << 1], id[MAXN], cnt[MAXN]; int height[MAXN]; char s[MAXN]; int n; void build_sa() { int m = 128; // 字符集大小，按实际调整 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) { int p = 0; for (int i = n - w + 1; i <= n; i++) id[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w; memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; i++) cnt[rk[id[i]]]++; for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i]; memcpy(oldrk, rk, sizeof(rk)); p = 0; for (int i = 1; i <= n; i++) { if (oldrk[sa[i]] == oldrk[sa[i-1]] && oldrk[sa[i] + w] == oldrk[sa[i-1] + w]) rk[sa[i]] = p; else rk[sa[i]] = ++p; } if (p == n) break; m = p; } } void build_height() { int k = 0; for (int i = 1; i <= n; i++) { if (rk[i] == 1) { height[rk[i]] = 0; continue; } if (k) k--; int j = sa[rk[i] - 1]; while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } }这段代码里 oldrk 数组要开两倍大小，因为比较第二关键字时可能访问到 n+w 的位置，越界会读到脏数据。这是我自己踩过的坑，开小了在本地跑没事，交上去随机 WA，查了半天。
2.4 用 SA 统计答案的完整流程与实测注意点
有了 sa 和 height，统计答案就是一行循环的事：
long long ans = 0; for (int i = 1; i <= n; i++) { ans += (n - sa[i] + 1) - height[i]; }注意 height[1] 对应排名第一的后缀，它前面没有后缀，所以 height[1] 应该是 0。上面 build_height 里对 rk[i]==1 的情况直接置 0，是对的。
实测下来有几个点要提醒。第一，答案要用 long long。n = 10^5 时，不同子串数量最坏接近 n(n+1)/2，大约 5×10^9，int 装不下。第二，如果字符串里有空格或特殊字符，字符集 m 要相应调整，或者干脆先做一次离散化把字符映射到 1..k。第三，倍增法在 n 比较小（比如 n=1）的时候要特判，否则 w 循环可能出问题。我一般会在读入后加一句 if (n == 1) { cout << 1; return 0; }。
SA 路线的整体复杂度是 O(n log n) 构造加 O(n) 统计，空间 O(n)。对于 n 到 10^6 的题目，倍增法可能会卡常数，这时候要么上 SA-IS，要么换 SAM。
3. 后缀自动机路线：从等价类直接数出子串
3.1 SAM 状态里到底存了什么
换一条路。后缀自动机是一个能识别字符串所有子串的最小 DFA，它的每个状态代表一组 endpos 相同的子串。什么叫 endpos 相同？就是这些子串在原串中出现的所有结束位置集合完全一样。同一组里的子串，长度是连续的，从某个最小值一直到该状态的 len 值。
这里 len 是 SAM 里每个状态记录的一个关键量：它表示这个状态所代表的子串集合中最长那个的长度。而 link 指针指向的是“当当前状态的子串继续变短、短到不再属于这个等价类时，跳到的那个状态”。所以 link 指向状态的 len，恰好是当前状态子串长度的下界减一。
于是当前状态贡献的不同子串数量就是 len[state] - len[link[state]]。把所有状态的这个差值加起来，就是整个串的不同子串总数。这个公式比 SA 那个还简洁，而且不需要排序，不需要 LCP，构建完直接扫一遍状态就行。
3.2 为什么每个状态恰好贡献 len 减 link 的 len
用一个具体串来感受。s = “ababa”，我们看 SAM 构建过程中某个状态。
假设某个状态 v 的 len 是 3，link 指向的状态 u 的 len 是 1。那么 v 代表的子串长度范围是 2 到 3，也就是长度为 2 和 3 的那些子串，它们共享同样的 endpos 集合。长度为 1 的子串属于 u 那个等价类。所以 v 贡献了 2 个不同子串。
这个逻辑对每个状态都成立，因为 SAM 的状态划分本身就是按 endpos 等价类来的，每个等价类里的子串长度连续，且不同等价类之间不会有重复的子串。把所有等价类的“长度跨度”加起来，自然就是不重不漏的总数。
这里有个常见误解：有人以为要遍历每个状态再枚举它代表的所有子串，那样复杂度就退化了。实际上根本不用枚举，len 减 link 的 len 直接就是数量，O(1) 算出来。
3.3 在线构建 SAM 的关键步骤与易错点
SAM 的构建是在线的，每加一个字符就扩展一次。核心操作是新建一个 cur 状态，然后沿着 link 往回跳，给没有对应转移的状态补上转移，直到遇到已经有转移的状态或者跳到根。如果遇到的状态已经有该字符的转移，还要判断是否需要克隆（clone）。
下面是一份常用的 SAM 模板：
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; // 开两倍 struct State { int len, link; int next[26]; } st[MAXN]; int sz, last; void sam_init() { st[0].len = 0; st[0].link = -1; memset(st[0].next, -1, sizeof(st[0].next)); sz = 1; last = 0; } void sam_extend(int c) { int cur = sz++; st[cur].len = st[last].len + 1; memset(st[cur].next, -1, sizeof(st[cur].next)); int p = last; while (p != -1 && st[p].next[c] == -1) { 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; }几个容易翻车的点。第一，状态数组要开 2n，因为每次扩展最多新建两个状态（cur 和可能的 clone），开 n 会越界。第二，clone 状态的 next 数组必须从 q 完整复制，漏了任何一个转移都会导致后续匹配出错。第三，while 循环里更新转移的条件是 st[p].next[c] == q，不是 == -1，写错会死循环或者改错转移。第四，字符要映射到 0..25，如果原串是大写或混合，记得先转换。
3.4 统计答案与复杂度分析
构建完之后，统计就非常简单：
long long ans = 0; for (int i = 1; i < sz; i++) { ans += st[i].len - st[st[i].link].len; }从 1 开始遍历，跳过根节点 0，因为根不代表任何实际子串。每个状态加上自己的长度跨度，累加即可。
SAM 的构建是严格 O(n) 的，因为每个字符的扩展均摊下来是常数时间，虽然内层有 while 循环，但 link 的深度总变化量是线性的。统计也是 O(n)。空间上每个状态要存 26 个转移，n = 10^6 时内存会比较大，这时候可以用 map 或者哈希表来存转移，牺牲一点常数换空间。
对比一下两条路：SA 是 O(n log n) 时间、O(n) 空间，思路偏“排序后去重”；SAM 是 O(n) 时间、O(n×字符集) 空间，思路偏“等价类划分”。如果题目对时间卡得死且字符集小，SAM 更优；如果字符集很大或者你更熟悉 SA，SA 也完全够用。
4. 两条路的对拍验证与边界情况处理
4.1 用暴力对拍确认公式没写错
不管用哪种方法，写完一定要拿暴力对拍。暴力思路很简单：枚举所有子串塞进 set，最后输出 set 的大小。n 小的时候（比如 n ≤ 100）跑个几千组随机数据，两种方法和暴力都对一遍，能揪出绝大多数实现错误。
我一般会写一个随机字符串生成器，字符集取小一点（比如只有 ‘a’ 和 ‘b’），这样更容易触发重复子串多的情况，也更容易暴露 LCP 或 link 处理的边界问题。对拍的时候注意把两种方法的答案都设成 long long，避免溢出导致的假阴性。
对拍代码结构大致是：
// 暴力 set<string> S; for (int i = 0; i < n; i++) for (int j = i; j < n; j++) S.insert(s.substr(i, j - i + 1)); cout << S.size() << endl;跑上几百组，如果 SA 和 SAM 的输出都和暴力一致，基本可以放心。
4.2 全相同字符、单字符、空串这些坑
有几类边界数据特别容易出问题。第一类是全相同字符，比如 “aaaaa”。这时候 SA 的 height 数组会很大，SAM 的状态数会很少（因为所有子串的 endpos 结构很规整）。SA 做法里，全相同串的答案应该是 n，因为不同子串就是 a, aa, aaa, …, n 个 a。用公式验证：后缀长度和是 n+(n-1)+…+1 = n(n+1)/2，height 之和是 (n-1)+(n-2)+…+0 = n(n-1)/2，相减得 n，正确。
第二类是单字符，n=1。SA 的倍增循环可能不执行，height 全 0，答案 1。SAM 构建一个状态，len=1，link 指向根（len=0），贡献 1。都对。
第三类是空串，虽然题目一般不会给 n=0，但如果你写的函数被复用到别处，最好加个判断。空串的不同子串数量定义为 0。
第四类是字符集包含数字或符号。SA 的字符集 m 要覆盖所有出现的字符，或者先离散化。SAM 的 next 数组大小要按实际字符集开，如果字符集是 62（大小写加数字），开 26 就不够。
4.3 内存与常数优化的一些实战经验
n 比较大的时候，SA 的倍增法常数主要花在基数排序的几趟循环上。一个优化是把字符集 m 在每轮之后缩小到当前排名数 p，这样后续的计数数组不用清那么大。另一个优化是当 p == n 时提前 break，因为所有后缀已经区分开了。
SAM 的常数主要在 memset 和 memcpy 上。如果字符集小，用数组没问题；如果字符集大，建议把 next 换成 map 或者用链式前向星存转移。另外 clone 操作里的 memcpy 是 26 个 int，n 大时累计起来也不少，可以考虑只复制实际用到的转移。
还有一点，如果题目只要求答案而不需要保留 SAM 结构，可以在统计完之后直接释放，不过竞赛里一般不需要这么抠。
5. 这道题真正教会我的事
做完这道题之后我最大的感受是，字符串计数类问题的通用套路就是“找到一种不重不漏的划分方式”。SA 用排序把后缀排好，让重复只发生在相邻之间；SAM 用 endpos 等价类把子串分组，让每组内部长度连续且组间不重叠。两种划分方式不同，但都达到了同一个目的。
另一个体会是，公式越简洁，背后的结构越重要。Σ(len - len[link]) 这行代码谁都会写，但如果不理解 endpos 等价类，遇到需要按子串出现次数加权的变体题（比如求所有不同子串的出现次数之和）就会卡住。那种题需要在 SAM 上做拓扑排序累加 endpos 大小，或者用 SA 的单调栈统计每个 height 的贡献范围，都是从这个基础模型延伸出去的。
最后分享一个我自己的习惯：每学一个字符串算法，就拿“不同子串个数”这道题当试金石。能独立把 SA 和 SAM 两条路都写对、都对拍过，说明这个算法的核心算是真正掌握了。如果只能背模板而说不清为什么，那遇到变形题大概率还是要翻车。
