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(n1)/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 两种解法的选型对比对比维度后缀数组 LCP后缀自动机时间复杂度O(n log n) 构造 O(n) 计数O(n) 构造 O(n) 计数空间复杂度O(n) 但常数较大O(n) 但常数较小实现难度中等倍增法容易写错中等偏上link指针维护易出错扩展能力擅长处理与排序、区间相关的问题擅长处理子串出现次数、本质不同子串调试难度height数组边界容易出问题状态转移和clone操作容易漏如果只是单纯统计不同子串个数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)然后从位置ik和位置sa[rank[i]-1]k开始逐字符比较直到不匹配为止此时k就是height[rank[i]]。由于k最多减少n次增加也最多n次总比较次数是O(n)的。这个算法的精妙之处在于利用了后缀之间的连续性避免了每个位置都从头比较。我第一次写的时候没理解k-1的含义直接每个位置暴力比较结果TLE了。后来画了个图才明白相邻后缀的LCP变化是有界的这个界就是1。3.3 后缀自动机的状态与转移维护后缀自动机的构造是增量式的。假设已经建好了字符串前i个字符的SAM现在要加入第i1个字符c。步骤如下创建一个新状态curlen[cur] len[last] 1。然后从last开始沿着link指针往上走如果某个状态没有字符c的转移就把它指向cur。如果走到了空就把cur的link设为初始状态。如果某个状态p已经有字符c的转移设转移目标为q。此时如果len[p] 1 len[q]直接把cur的link设为q。否则需要克隆q得到clone把q的所有转移复制给clonelen[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[ik] s[jk]) 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次取平均时间结果如下nSALCP耗时(ms)SAM耗时(ms)答案规模100021约50万10000188约5000万10000021095约50亿可以看到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[1]未置0检查height数组初始化答案偏大基数排序桶未清空每轮排序前memset cnt数组越界第二关键字构造时下标越界检查n-k1到n的边界死循环rank更新时p未递增确认每轮p从1开始结果不稳定字符集大小m未更新每轮结束后m p我印象最深的一次是height数组求出来全是0查了半天发现是rank数组在倍增过程中被覆盖了。后来我把old_rk单独开了一个数组每次更新rank之前先memcpy一份问题就解决了。这个坑很隐蔽因为rank错了之后sa也会错但sa的错误不一定立刻暴露可能要到计数阶段才发现答案不对。5.2 后缀自动机常见错误速查表现象可能原因排查方法答案偏小clone状态未计入遍历时从2到tot全算答案偏大link指针成环检查clone的link赋值转移丢失clone未复制nxtmemcpy整个nxt数组状态数超限数组开太小开到2n5字符映射错未减去a确认字符集偏移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, 字符集大小)。如果字符集是256n是10的5次方cnt开到10的5次方就够了。但每轮memset整个cnt数组会浪费一些时间可以只清空用到的部分。SAM的nxt数组如果开成int nxt[2*MAXN][26]内存大约是210^526*4字节约20MB可以接受。如果字符集更大可以改成mapint,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(n1)/2因为没有任何重复。这两个极端情况能快速验证代码的正确性。如果这两个都过了再跑随机对拍基本就稳了。