1. 从一道经典题看透子串计数的本质

第一次碰到“不同子串个数”这个问题，是在帮一个做文本分析的朋友处理日志去重的时候。他手里有几百万条短文本，想统计其中到底有多少种不同的片段组合，用来判断数据源的多样性。当时我脑子里第一反应就是后缀数组加LCP，或者后缀自动机，这两个东西几乎是这类问题的标准答案。后来在题库里刷到P2408这道题，发现它把两种解法放在一起对比，正好是一个绝佳的切入点，能把子串计数这件事从原理到实现彻底讲清楚。

这道题的核心需求非常直接：给定一个长度为n的字符串，统计它所有本质不同的子串数量。所谓本质不同，就是内容不一样，位置不同但内容相同的只算一个。比如字符串“abab”，它的子串有“a”“b”“ab”“ba”“aba”“bab”“abab”，去重之后是7个。n的范围通常到10的5次方甚至更大，暴力枚举所有子串再塞进哈希表去重，时间复杂度是O(n²)级别，空间也扛不住，必须用更聪明的数据结构。

适合谁来参考这篇内容？如果你已经学过字符串哈希、KMP或者字典树，想进一步掌握后缀数组和后缀自动机这两个进阶工具，那这篇就是为你准备的。如果你只是听说过SA和SAM的名字，不知道它们怎么用在计数问题上，我也会从最直观的几何意义讲起，尽量不堆公式。两种解法我都会给出完整的思路推导、代码框架和实际调试中踩过的坑，你可以直接拿去改改就能用在自己的项目里。

2. 两种解法的整体设计思路拆解

2.1 为什么暴力枚举一定会超时

先算一笔账。长度为n的字符串，子串总数是n(n+1)/2。n等于10的5次方时，子串数量大约是50亿个。就算每个子串用O(1)时间哈希并插入集合，50亿次操作在现代计算机上也要几十秒甚至几分钟，内存更是放不下这么多哈希值。更致命的是，很多子串会重复，暴力法做了大量无用功。所以必须找到一种方式，让每个本质不同的子串只被“数”一次，而不是先枚举再过滤。

这里的关键洞察是：所有子串都是某个后缀的前缀。字符串的每一个后缀，它的所有前缀就构成了全部子串。如果我们能把所有后缀按字典序排好，那么相邻后缀之间的公共前缀部分就是重复计数的来源。这个思路直接导向后缀数组加LCP的解法。

另一个角度是从字符串的自动机构造出发。后缀自动机把字符串的所有子串压缩到一个有向无环图中，每个状态代表一组endpos相同的子串，状态里记录了这个等价类中substring的长度区间。所有状态的长度区间大小之和，恰好就是本质不同子串的总数。这个思路更偏向组合数学的计数。

2.2 后缀数组加LCP的计数逻辑

后缀数组的核心是把所有后缀按字典序排序，得到sa数组和rank数组。排完序之后，相邻两个后缀的LCP（最长公共前缀）就是它们共享的重复前缀长度。假设排序后的后缀依次是suffix[sa[1]], suffix[sa[2]], ..., suffix[sa[n]]，对于第i个后缀，它能贡献的新子串数量是：它的总长度减去它与前一个后缀的LCP长度。

为什么是这样？因为第i个后缀的所有前缀中，长度小于等于LCP的那部分，已经作为前一个后缀的前缀出现过了，属于重复。只有长度超过LCP的那些前缀，才是第一次出现的新子串。把所有后缀的新贡献加起来，就是答案。

用公式表达：answer = Σ (n - sa[i] - height[i])，其中height[i]是排名第i的后缀与排名第i-1的后缀的LCP长度，height[1]定义为0。这个公式非常简洁，但背后是排序加去重的完整逻辑。

2.3 后缀自动机的计数逻辑

后缀自动机把字符串的所有子串组织成状态和转移。每个状态代表一个endpos等价类，这个等价类中的所有子串长度构成一个连续区间[minlen, maxlen]。这个区间的大小是maxlen - minlen + 1，也就是这个状态贡献的不同子串数量。把所有状态的这个值加起来，就是答案。

为什么每个状态贡献的是长度区间大小？因为同一个状态内的所有子串，它们的endpos集合完全相同，这意味着它们在字符串中出现的位置模式一模一样。长度不同的子串内容必然不同，所以这个区间里的每个长度对应一个唯一子串。不同状态之间的子串也不会重复，因为endpos集合不同。所以总和就是本质不同子串数。

SAM的构造是增量的，每加入一个字符，最多新增两个状态，总状态数不超过2n。构造完之后遍历所有状态累加len[state] - len[link[state]]即可。这个解法的时间复杂度和空间复杂度都是O(n)，非常优雅。

2.4 两种解法的选型对比

如果只是单纯统计不同子串个数，SAM在时间和代码简洁度上略占优势。但如果后续还要处理“第k小子串”“子串出现次数”等问题，SAM的扩展性更强。SA则在处理“多个字符串的公共子串”“子串排序”等问题时更自然。实际比赛中，两种都要会，根据题目附加条件灵活选择。

3. 核心细节解析与实操要点

3.1 后缀数组倍增构造的关键细节

后缀数组的倍增法核心是：先按第一个字符排序，然后按前2个字符、前4个字符、前8个字符依次排序，直到所有后缀的排名都不相同。每一轮利用上一轮的rank作为第一关键字，上一轮rank向后偏移k位作为第二关键字，做基数排序。

这里有几个容易翻车的点。第一，第二关键字为空的情况要排在前面，具体做法是在构造第二关键字序列时，把位置n-k到n-1的rank视为0，并且这些位置要优先放入排序队列。第二，基数排序的桶大小要开到max(n, 字符集大小)，并且每次排序前要清空计数数组。第三，rank数组的更新要用一个临时数组，不能直接在原数组上改，否则同一轮中后面的位置会读到已经更新的值。

我实测下来，倍增法在n等于10的5次方时，大约需要17轮，每轮基数排序O(n)，总时间在100毫秒以内，完全够用。但如果n到了10的6次方，倍增法就有点吃力了，这时候可以考虑DC3或者SA-IS，不过那是另一个话题了。

3.2 LCP数组的线性求法

求出sa和rank之后，LCP数组（也就是height数组）可以用一个非常巧妙的线性方法求出来。核心性质是：height[rank[i]] >= height[rank[i-1]] - 1。也就是说，从位置i开始的后缀与它前一个后缀的LCP，至少比从位置i-1开始的后缀与它前一个后缀的LCP少1。

利用这个性质，我们按原字符串位置从0到n-1遍历，维护一个当前LCP长度k。如果rank[i]等于0（即这个后缀排第一），k直接置0。否则，让k取max(k-1, 0)，然后从位置i+k和位置sa[rank[i]-1]+k开始逐字符比较，直到不匹配为止，此时k就是height[rank[i]]。由于k最多减少n次，增加也最多n次，总比较次数是O(n)的。

这个算法的精妙之处在于利用了后缀之间的连续性，避免了每个位置都从头比较。我第一次写的时候没理解k-1的含义，直接每个位置暴力比较，结果TLE了。后来画了个图才明白，相邻后缀的LCP变化是有界的，这个界就是1。

3.3 后缀自动机的状态与转移维护

后缀自动机的构造是增量式的。假设已经建好了字符串前i个字符的SAM，现在要加入第i+1个字符c。步骤如下：创建一个新状态cur，len[cur] = len[last] + 1。然后从last开始沿着link指针往上走，如果某个状态没有字符c的转移，就把它指向cur。如果走到了空，就把cur的link设为初始状态。如果某个状态p已经有字符c的转移，设转移目标为q。此时如果len[p] + 1 == len[q]，直接把cur的link设为q。否则，需要克隆q得到clone，把q的所有转移复制给clone，len[clone] = len[p] + 1，然后把q和cur的link都指向clone，并且从p开始往上，把所有指向q的c转移改成指向clone。

这里最容易出错的是clone操作。clone要继承q的所有转移和link，但len要改成len[p]+1。另外，修改转移的时候只能改那些原本指向q的，不能改指向其他状态的。我踩过的坑是忘记把q的link也指向clone，导致后续构造时link链断裂，计数结果偏大。

3.4 计数时的边界处理

对于SA解法，计数公式是Σ(n - sa[i] - height[i])。注意height[1]必须是0，因为排名第一的后缀前面没有其他后缀，它的所有前缀都是新的。另外，sa数组和height数组的下标通常从1开始，而原字符串下标从0开始，转换的时候要小心。我习惯把字符串前面加一个特殊字符，让下标从1开始，这样sa[i]直接就是后缀的起始位置，n - sa[i]就是后缀长度。

对于SAM解法，计数公式是Σ(len[state] - len[link[state]])。初始状态不参与计数，因为它的len是0。另外，clone状态的len也要参与计数，因为它代表了新的长度区间。有些实现会忘记把clone加入统计，导致答案偏小。我一般是在构造完SAM之后，从状态1到状态tot遍历，累加len[i] - len[link[i]]，这样不会漏掉clone。

4. 完整实操过程与核心环节实现

4.1 后缀数组解法的完整代码框架

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int sa[MAXN], rk[MAXN], old_rk[MAXN], cnt[MAXN], height[MAXN]; int n; char s[MAXN]; void build_sa() { int m = 256; // 第一轮：按第一个字符排序 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 k = 1; k <= n; k <<= 1) { int p = 0; // 第二关键字排序 for (int i = n - k + 1; i <= n; i++) old_rk[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] > k) old_rk[++p] = sa[i] - k; // 第一关键字基数排序 memset(cnt, 0, sizeof(cnt)); for (int i = 1; i <= n; i++) cnt[rk[i]]++; for (int i = 1; i <= m; i++) cnt[i] += cnt[i-1]; for (int i = n; i >= 1; i--) sa[cnt[rk[old_rk[i]]]--] = old_rk[i]; // 更新rank memcpy(old_rk, rk, sizeof(rk)); rk[sa[1]] = 1; p = 1; for (int i = 2; i <= n; i++) { if (old_rk[sa[i]] == old_rk[sa[i-1]] && old_rk[sa[i]+k] == old_rk[sa[i-1]+k]) 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) { k = 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; } } int main() { scanf("%s", s + 1); n = strlen(s + 1); build_sa(); build_height(); long long ans = 0; for (int i = 1; i <= n; i++) { ans += (n - sa[i] + 1) - height[i]; } printf("%lld\n", ans); return 0; }

这段代码里，n - sa[i] + 1是排名第i的后缀的长度，减去height[i]就是新贡献。注意字符串下标从1开始，所以长度计算要加1。基数排序的桶大小m在每轮结束后更新为当前rank的最大值，这样后续轮次的桶不会开得过大。

4.2 后缀自动机解法的完整代码框架

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; int len[MAXN], link[MAXN], nxt[MAXN][26]; int tot = 1, last = 1; char s[MAXN]; void sam_extend(int c) { int cur = ++tot; len[cur] = len[last] + 1; int p = last; while (p && !nxt[p][c]) { nxt[p][c] = cur; p = link[p]; } if (!p) { link[cur] = 1; } else { int q = nxt[p][c]; if (len[p] + 1 == len[q]) { link[cur] = q; } else { int clone = ++tot; len[clone] = len[p] + 1; link[clone] = link[q]; memcpy(nxt[clone], nxt[q], sizeof(nxt[q])); while (p && nxt[p][c] == q) { nxt[p][c] = clone; p = link[p]; } link[q] = link[cur] = clone; } } last = cur; } int main() { scanf("%s", s + 1); int n = strlen(s + 1); for (int i = 1; i <= n; i++) { sam_extend(s[i] - 'a'); } long long ans = 0; for (int i = 2; i <= tot; i++) { ans += len[i] - len[link[i]]; } printf("%lld\n", ans); return 0; }

SAM的代码更短，但clone操作是精髓。注意nxt数组的大小要开到2n，因为总状态数不超过2n。字符集如果是小写字母，开26就够了；如果是任意字符，可以用map或者把字符集离散化。计数时从状态2开始遍历，因为状态1是初始状态，len为0，不贡献子串。

4.3 两个解法的实测对比数据

我用随机生成的字符串做了几组测试，n分别取1000、10000、100000，字符集为小写字母。每组跑10次取平均时间，结果如下：

可以看到SAM在时间上大约快一倍，主要因为SA的倍增法有log因子，而SAM是纯线性的。但SA的代码更模板化，写熟了之后不容易出错。SAM的clone操作如果写错，调试起来比较痛苦。实际选择时，如果时间限制宽松，SA更稳妥；如果追求极致性能，SAM更优。

4.4 答案的数据类型选择

不同子串的数量级是O(n²)的。n等于10的5次方时，答案大约是50亿，超过了32位整数的范围。所以计数变量必须用long long。我见过有人用int存答案，结果n稍微大一点就溢出变成负数，排查了半天才发现是类型问题。另外，中间计算n - sa[i] + 1的时候，如果n是int，结果也是int，但累加到long long没问题。SAM的len[i] - len[link[i]]也是int范围内的差值，累加用long long即可。

5. 常见问题与排查技巧实录

5.1 后缀数组常见错误速查表

我印象最深的一次是height数组求出来全是0，查了半天发现是rank数组在倍增过程中被覆盖了。后来我把old_rk单独开了一个数组，每次更新rank之前先memcpy一份，问题就解决了。这个坑很隐蔽，因为rank错了之后sa也会错，但sa的错误不一定立刻暴露，可能要到计数阶段才发现答案不对。

5.2 后缀自动机常见错误速查表

SAM最坑的地方是clone的link赋值顺序。正确的顺序是：先设len[clone]，再复制nxt，再设link[clone] = link[q]，然后修改p链上的转移，最后设link[q] = link[cur] = clone。如果顺序错了，比如先改了link[q]再复制nxt，就可能出现link指向错误。我建议把clone操作单独写成一个函数，每次调用时逐行对照模板，减少手误。

5.3 两种解法的选择建议

如果题目只问不同子串个数，SAM代码更短，跑得更快，优先选SAM。如果题目还要求输出字典序第k小的子串，或者要求子串的出现次数，SAM的转移图可以直接做DP，更方便。如果题目涉及多个字符串的公共子串，或者需要按后缀排序来处理，SA更自然。另外，如果字符集很大（比如包含所有ASCII字符），SAM的nxt数组开不下，需要用map或者哈希表，这时候SA的基数排序反而更简单，因为SA不依赖字符集大小，只依赖rank的相对顺序。

5.4 内存与常数的优化技巧

SA的基数排序中，cnt数组的大小是max(n, 字符集大小)。如果字符集是256，n是10的5次方，cnt开到10的5次方就够了。但每轮memset整个cnt数组会浪费一些时间，可以只清空用到的部分。SAM的nxt数组如果开成int nxt[2*MAXN][26]，内存大约是210^526*4字节，约20MB，可以接受。如果字符集更大，可以改成map<int,int>或者用链式前向星存转移，但会牺牲一些速度。

我在实际项目中处理过一个n等于5*10^5的字符串，SA的倍增法跑了大约1.2秒，SAM跑了0.5秒。后来我把SA的基数排序改成用std::sort加比较函数，反而更慢，因为比较函数里有log因子。所以倍增法加基数排序仍然是SA构造的最优选择之一。

5.5 调试时的小技巧

对于SA，我习惯先输出sa和height数组，手动验证几个后缀的排序和LCP是否正确。比如字符串“aabaaaab”，手动算一下前几个后缀的LCP，和程序输出对比。对于SAM，我会输出每个状态的len和link，画成树状结构，检查link链是否形成一棵以初始状态为根的树。如果link链有环，说明clone操作有问题。另外，可以用一个暴力程序对拍，n取小一点（比如10以内），随机生成字符串，比较两个解法的答案是否一致。对拍是发现逻辑错误最快的方法。

6. 从这道题延伸出的实际应用场景

子串计数看起来是一道算法题，但它在实际工程中的影子随处可见。比如日志分析中，统计不同请求路径的模式数量，可以把路径看作字符串，不同子串就是不同的路径片段。再比如生物信息学中，DNA序列由A、T、C、G组成，统计不同子串的数量可以用来评估序列的复杂度。还有文本去重、代码克隆检测、用户行为序列分析等场景，都会用到类似的技术。

后缀数组和后缀自动机作为字符串处理的瑞士军刀，掌握它们不仅仅是为了刷题。我在做一个跨平台系统的日志聚类功能时，就用SAM统计了不同日志模板的数量，然后根据状态的出现频率做聚类，效果比简单的哈希去重好很多，因为SAM能捕捉到子串之间的包含关系。如果你正在处理文本数据，建议把这两个工具都纳入工具箱，根据具体需求灵活选用。

最后分享一个我个人的习惯：每次写完SA或SAM的代码，我都会用几个边界用例测一下，包括空串、单字符、全相同字符、全不同字符、以及随机字符串。全相同字符的答案是n，因为所有子串都是“a”“aa”“aaa”这种，数量正好是n。全不同字符的答案是n(n+1)/2，因为没有任何重复。这两个极端情况能快速验证代码的正确性。如果这两个都过了，再跑随机对拍，基本就稳了。