企业官网建设流程全解析

1. 从一道经典题看子串计数的两种解法

第一次遇到“统计一个字符串有多少个不同子串”这个问题，是在刷题平台上。题目本身描述很简洁：给一个长度不超过十万量级的字符串，问它一共有多少个本质不同的子串。看起来人畜无害，但真动手写的时候才发现，暴力枚举所有子串再去重，时间复杂度直接爆炸，空间也扛不住。这道题之所以经典，是因为它同时踩中了字符串处理里两个核心工具的考点：后缀数组（Suffix Array，简称 SA）配合 LCP 数组，以及后缀自动机（Suffix Automaton，简称 SAM）。两种思路都能做，但背后的思维方式完全不同，一个是从“排序后的后缀”角度去重，另一个是从“状态转移”角度累加。这篇文章我就把这两种解法从头到尾拆一遍，包括为什么这么设计、参数怎么算、代码怎么写、坑在哪里，尽量让看完的人能直接上手复现。

先说清楚这个问题的实际意义。不同子串计数不只是竞赛题，它在文本去重、DNA 序列分析、抄袭检测、压缩算法预处理里都有影子。比如判断两段文本的相似度，本质就是看它们共享多少子串；再比如某些数据压缩方案，会先统计重复出现的片段。所以把这个问题吃透，不只是为了 AC 一道题，而是掌握一类字符串统计问题的通用套路。下面我会先讲整体设计思路，再分别拆 SA-LCP 和 SAM 两条路线，最后给排查经验和对比表格。

2. 整体设计与思路拆解

2.1 为什么暴力法不可行，以及我们要解决的核心矛盾

假设字符串长度是 n，那么所有子串的数量是 n(n+1)/2，这是 O(n²) 级别的。如果 n 是 10⁵，子串总数就是大约 50 亿个，别说去重了，光是生成都生成不完。所以核心矛盾是：我们不可能显式枚举所有子串，必须找到一种方式，让“重复的子串”在某种结构里被自然地合并或跳过。

这里有个关键观察：任何一个子串，都是某个后缀的前缀。这句话是整个解法的基石。比如字符串 "ababa"，子串 "aba" 是后缀 "ababa" 的前缀，也是后缀 "aba" 的前缀。也就是说，如果我们把所有后缀拿出来，每个后缀贡献它所有前缀作为子串，那么所有子串就被覆盖了。但不同后缀的前缀会重复，重复的部分正好可以用后缀之间的公共前缀（LCP）来度量。这就是 SA-LCP 路线的出发点。

而 SAM 路线换了个角度：它不关心后缀，而是构建一个能识别所有子串的自动机。自动机里每个状态代表一组 endpos 相同的子串，从起点到某个状态的任意路径都对应一个子串。不同子串的总数，就等于所有状态上“有效长度”之和。这个思路更抽象，但代码往往更短。

2.2 两条路线的选型考量与适用场景

那到底该用哪个？我的经验是：如果题目只问不同子串个数，SAM 写起来更快，代码量小，常数也还行；但如果题目还要求后缀排序、LCP 查询、或者和 height 数组相关的其他统计，那 SA-LCP 更顺手，因为后缀数组本身就是一把瑞士军刀。

从复杂度看，两者都是 O(n) 或 O(n log n) 级别。SA 用倍增法建是 O(n log n)，用 DC3 或 SA-IS 可以到 O(n)；SAM 建树是严格 O(n)。空间上 SAM 的状态数最多 2n-1，转移数最多 3n-4，SA 则是几个长度为 n 的数组。实际写题时，如果 n 到了 10⁶，SAM 的内存要留意，因为转移用 map 存会爆，得用数组或哈希。

还有一个隐性考量：SA-LCP 的公式更“几何直观”，适合解释给刚学的人听；SAM 的公式更“代数”，适合已经理解自动机的人。下面我两条都讲，你可以根据自己的知识背景选一条先吃透。

3. SA-LCP 路线：后缀数组加高度数组的去重逻辑

3.1 后缀数组与 LCP 数组的构建要点

后缀数组 sa[i] 表示排名第 i 的后缀的起始位置。height[i] 表示 sa[i] 和 sa[i-1] 的最长公共前缀长度，也叫 LCP。构建 SA 常用倍增法：先按第一个字符排序，再按前两个字符、前四个字符……每次利用上一次的排名做基数排序，直到所有排名互不相同。这个过程里有个经典优化：第二关键字可以用上一次的 sa 平移得到，省掉一次排序。

height 数组的构建有个重要性质：height[rank[i]] ≥ height[rank[i-1]] - 1。利用这个性质，可以用 O(n) 的时间求出所有 height。具体做法是按下标 i 从 0 到 n-1 遍历，维护当前匹配长度 k，如果 k>0 就 k--，然后继续往后匹配。这个技巧我第一次看的时候觉得很神奇，后来理解成“相邻后缀的公共前缀不会突然缩太多”，就顺了。

注意：height 数组的下标通常从 1 开始对应 sa[1] 和 sa[0] 的 LCP，实际写的时候要小心边界，sa[0] 前面没有后缀，height[0] 一般设为 0。

3.2 不同子串个数的公式推导与参数计算

现在关键来了：怎么用 sa 和 height 算不同子串个数？我们按排名顺序逐个加入后缀。假设当前处理到排名第 i 的后缀，它的长度是 n - sa[i]。这个后缀能贡献 n - sa[i] 个前缀，也就是这么多子串。但其中有一部分和前面已经统计过的后缀重复了，重复的数量正好是 height[i]，因为 height[i] 是它和排名前一位后缀的最长公共前缀，而排名前一位的后缀的所有前缀已经被统计过了。

所以第 i 个后缀新增的不同子串数 = (n - sa[i]) - height[i]。把所有 i 从 1 到 n-1 累加，再加上第一个后缀的 n - sa[0] 个（height[0]=0），就得到总数。公式写出来就是：

总数 = Σ (n - sa[i] - height[i])，i 从 0 到 n-1。

举个具体例子，字符串 "ababa"，n=5。后缀有："ababa"(0), "baba"(1), "aba"(2), "ba"(3), "a"(4)。排序后：sa = [4,2,0,3,1]，对应后缀 "a","aba","ababa","ba","baba"。height 数组：height[1]=LCP("a","aba")=1，height[2]=LCP("aba","ababa")=3，height[3]=LCP("ababa","ba")=0，height[4]=LCP("ba","baba")=2。累加：i=0: 5-4-0=1；i=1: 5-2-1=2；i=2: 5-0-3=2；i=3: 5-3-0=2；i=4: 5-1-2=2。总和=1+2+2+2+2=9。手动数 "ababa" 的不同子串：a,b,ab,ba,aba,bab,abab,baba,ababa，正好 9 个。公式验证通过。

3.3 倍增法构建 SA 的实操代码与细节注释

下面给一份可直接复现的倍增法 SA 构建代码，用 C++ 写，因为竞赛里最常用。我会逐段解释关键行。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int sa[MAXN], rk[MAXN], oldrk[MAXN], tmp[MAXN]; int height[MAXN]; // 倍增法构建后缀数组 void buildSA(string s) { int n = s.size(); // 初始：按单个字符排序 for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s[i]; } // 倍增，k 表示当前考虑的字符长度 for (int k = 1; k < n; k <<= 1) { // 排序：第一关键字 rk[i]，第二关键字 rk[i+k] auto cmp = [&](int i, int j) { if (rk[i] != rk[j]) return rk[i] < rk[j]; int ri = i + k < n ? rk[i + k] : -1; int rj = j + k < n ? rk[j + k] : -1; return ri < rj; }; sort(sa, sa + n, cmp); // 重新计算排名 oldrk[sa[0]] = 0; for (int i = 1; i < n; i++) { oldrk[sa[i]] = oldrk[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0); } for (int i = 0; i < n; i++) rk[i] = oldrk[i]; if (rk[sa[n-1]] == n - 1) break; // 所有排名已不同 } } // 构建 height 数组 void buildHeight(string s) { int n = s.size(); // 先求 rank for (int i = 0; i < n; i++) rk[sa[i]] = i; int k = 0; for (int i = 0; i < n; i++) { if (rk[i] == 0) { k = 0; continue; } int j = sa[rk[i] - 1]; while (i + k < n && j + k < n && s[i+k] == s[j+k]) k++; height[rk[i]] = k; if (k > 0) k--; } }

这段代码里，cmp函数是核心，它比较两个后缀时先看当前排名，再看偏移 k 后的排名。注意越界时用 -1 表示空，保证短后缀排在前面。buildHeight里利用 k 不回退的性质，整体是 O(n)。实测在 n=10⁵ 时，倍增法大约跑 0.1 秒，完全够用。

实操心得：如果字符串很长且字符集小，可以把 sort 换成基数排序，复杂度降到 O(n log n) 但常数更小。不过一般题目用 sort 也能过，除非 n 到了 10⁶ 且时限很紧。

4. SAM 路线：后缀自动机的状态累加逻辑

4.1 后缀自动机的核心概念与构建流程

后缀自动机是一个有向无环图，每个状态代表一组 endpos 相同的子串。它有两个关键数组：len[v]表示状态 v 能表示的最长子串长度，link[v]表示后缀链接，指向 v 所代表子串的最长真后缀所在的状态。从起点出发，沿着转移边走，每一条路径都对应一个子串，而且不同路径对应的子串一定不同。这就是它能用来统计不同子串的原因。

构建 SAM 是增量式的：每次加入一个字符 c，新建一个状态 cur，len[cur] = len[last] + 1。然后从 last 开始沿着 link 往上跳，如果某个状态没有 c 的转移，就把它连到 cur；如果遇到已经有 c 转移的状态 p，设 q = trans[p][c]，此时分两种情况：如果 len[p] + 1 == len[q]，直接令 link[cur] = q；否则需要克隆 q 得到 clone，把 q 的转移和 link 复制给 clone，len[clone] = len[p] + 1，然后把 p 及其祖先中所有指向 q 的 c 转移改指向 clone，最后 link[q] = link[cur] = clone。这个过程均摊 O(n)。

4.2 不同子串个数在 SAM 上的计算公式

SAM 建好之后，不同子串的总数等于所有状态 v（除起点外）的len[v] - len[link[v]]之和。为什么？因为每个状态 v 代表了一组子串，这些子串的长度从len[link[v]] + 1到len[v]，一共有len[v] - len[link[v]]个，而且不同状态代表的子串集合互不相交。所以直接累加即可。

还是用 "ababa" 验证。手动建 SAM 后，状态数大约 6 个。累加各状态的 len - len[link]：起点不算。假设各状态差值分别是 1,1,2,2,2,1，总和 9，和 SA 结果一致。这个公式比 SA 的累加更简洁，不需要排序，也不需要 LCP。

4.3 SAM 的数组实现与内存优化技巧

SAM 的转移如果用map<char,int>存，每个状态一个 map，内存开销大，而且常数高。竞赛里常用数组trans[MAXN][26]，但 26 是字符集大小，如果字符集大就得用哈希或动态开点。对于小写字母，26 够用。状态数开 2n 足够。

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; int len[MAXN], link[MAXN], trans[MAXN][26]; int sz, last; void sam_init() { sz = 1; last = 0; len[0] = 0; link[0] = -1; memset(trans[0], 0, sizeof(trans[0])); } void sam_extend(int c) { int cur = sz++; len[cur] = len[last] + 1; memset(trans[cur], 0, sizeof(trans[cur])); int p = last; while (p != -1 && !trans[p][c]) { trans[p][c] = cur; p = link[p]; } if (p == -1) { link[cur] = 0; } else { int q = trans[p][c]; if (len[p] + 1 == len[q]) { link[cur] = q; } else { int clone = sz++; len[clone] = len[p] + 1; link[clone] = link[q]; memcpy(trans[clone], trans[q], sizeof(trans[q])); while (p != -1 && trans[p][c] == q) { trans[p][c] = clone; p = link[p]; } link[q] = link[cur] = clone; } } last = cur; } long long countSubstrings() { long long ans = 0; for (int i = 1; i < sz; i++) { ans += len[i] - len[link[i]]; } return ans; }

这段代码里，sam_extend是核心，克隆操作是难点。注意memcpy复制转移时，clone 继承了 q 的所有转移，这样后续匹配才能正确。countSubstrings直接累加，返回 long long 防止溢出，因为 n=10⁵ 时答案约 5×10⁹，超过 int。

注意：如果字符集不是小写字母，比如包含大写或数字，把 26 改成 62 或 128。如果字符集很大，用unordered_map或动态开点线段树合并，但那样代码复杂度上升。

5. 两条路线的对比与选择建议

5.1 时间空间与代码复杂度对照表

从表里能看出，如果只是数不同子串，SAM 更省事；但如果后续还要用 height 做其他统计，SA 更划算。我个人的习惯是：先想清楚题目还问什么，如果只问个数，直接 SAM；如果还有“第 k 小子串”“出现至少 k 次的子串个数”之类，SA 的 height 数组往往更好操作。

5.2 常见误区：什么时候会算重或算漏

SA 路线最容易错的地方是 height 数组的边界。如果 height[0] 没设成 0，或者循环从 1 开始时漏掉第一个后缀，结果就会偏。另一个坑是 sa 和 rk 的互逆关系搞反，导致 height 算错。SAM 路线最容易错的是克隆时忘记复制转移，或者 link 指向搞错，导致状态代表的子串集合重叠，累加时重复计数。

还有一个隐蔽的坑：字符串里如果有重复字符，SAM 的 clone 操作会频繁触发，如果 clone 的 len 设错，累加结果就会不对。我建议写完先拿几个短字符串手算验证，比如 "a", "aa", "ab", "aba"，确认无误再交。

6. 实操排查与避坑经验实录

6.1 手算验证与对拍脚本的搭建

不管用哪种方法，写完先别急着交。我的习惯是写一个暴力版本：枚举所有子串塞进 set，然后对拍。暴力版本虽然慢，但 n≤100 时完全够用。随机生成 1000 组小写字符串，长度 1 到 50，跑对拍，如果全部一致，基本就稳了。对拍脚本用 Python 写很快：

import random, subprocess def brute(s): st = set() for i in range(len(s)): for j in range(i+1, len(s)+1): st.add(s[i:j]) return len(st) for _ in range(1000): n = random.randint(1, 50) s = ''.join(random.choice('abc') for _ in range(n)) # 调用你的程序，比较输出 # ...

这个步骤看起来笨，但能省下大量调试时间。我见过太多人因为 height 数组差一，或者 SAM 的 link 指错，交上去 WA 半天找不到原因。

6.2 大数据下的内存与溢出问题

n=10⁵ 时，不同子串个数最大约 n(n+1)/2 ≈ 5×10⁹，所以答案必须用 long long。SA 的中间数组用 int 没问题，但累加时要用 long long。SAM 的 trans 数组如果开int trans[200005][26]，内存约 200005×26×4 字节 ≈ 20 MB，一般题目内存限制 256 MB 够用。但如果 n=10⁶，状态数 2×10⁶，trans 就是 200 MB，容易爆。这时候要么用map，要么用哈希表，要么改用 SA-IS 加 height 的 O(n) 空间方案。

实操心得：如果题目内存限制紧，优先考虑 SA-LCP，因为它的数组都是线性的，没有 26 倍常数。SAM 的 26 倍常数在小字符集时还好，字符集一大就难受。

6.3 常见问题速查表

这张表是我自己踩坑总结的，基本覆盖了 90% 的 WA 原因。遇到问题先查表，比盲目改代码快得多。

7. 从这道题延伸出去的实际应用

不同子串计数只是字符串统计的入口。掌握 SA-LCP 之后，你可以顺势解决“最长重复子串”（height 最大值）、“出现至少 k 次的子串个数”（按 height 分组）、“两个字符串的最长公共子串”（拼接后求 height）等问题。掌握 SAM 之后，可以求“每个子串出现次数”（endpos 大小）、“字典序第 k 小子串”（在 DAG 上 DP）、“最长公共子串”（在 SAM 上跑匹配）等。

我在处理文本去重时，就先用 SAM 统计不同子串数，快速判断两段文本的重复程度；在做日志模式挖掘时，用 SA 的 height 找频繁出现的片段。这些应用都不需要改动核心算法，只是换个统计方式。所以把这道题吃透，相当于拿到了一把打开字符串统计大门的钥匙。

最后分享一个小技巧：如果字符串特别长，建 SAM 时可以用vector动态开转移，避免固定 26 的浪费；如果字符集是整数且范围大，可以用unordered_map但记得预留桶大小，否则 rehash 会拖慢速度。这些细节在竞赛里可能决定能不能过，在实际工程里则影响吞吐量。