构建SAM必须维护link和len，否则无法正确拓扑转移；link指向最长真后缀状态以支撑parent树计数，len标识该状态最长子串长度，二者在新建/克隆节点时必须显式设置且不可遗漏。
构建 SAM 时必须维护 link 和 len，否则无法正确拓扑转移
构建 SAM 的核心是增量插入字符，每个新状态必须记录最长长度 len 和后缀链接 link。漏掉 link 就没法做 parent 树上的计数聚合。常见错误是只存了转移边（next 数组），却没在克隆节点或新建节点时同步设置 link 和 len。
实操建议：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用结构体封装每个状态：
struct State { int len, link; map<char int> next; };</char> - 初始状态
last = 0，st[0].len = 0，st[0].link = -1；每次插入后更新last - 克隆节点时：新节点
cur的len必须设为st[p].len + 1，不能直接拷贝st[p].len -
link不是凭空连的——它指向的是当前字符串的最长真后缀所对应的状态，必须通过沿link回跳找到第一个满足st[p].next[c] == q的p，再把st[q].link = clone
统计每个子串出现次数得靠 cnt 数组 + 拓扑序反向累加
SAM 中每个状态代表一组 endpos 等价类，其 cnt 表示该状态对应的所有子串在原串中总共出现了多少次（即 endpos 集合大小）。但初始时只有叶子状态（即对应某个前缀结尾的位置）的 cnt 是 1，其余为 0；必须按 len 从大到小排序（即 parent 树的拓扑逆序），把每个状态的 cnt 加到 st[i].link 对应状态上。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 建完 SAM 后，先用桶排序按
len分组（因为len范围是 [0, n]，O(n) 可排） - 倒序遍历所有状态索引：
for (int i = sz; i > 0; i--) { int u = rk[i]; cnt[st[u].link] += cnt[u]; } - 注意：只有显式插入位置（即每次
last指向的状态）才初始化cnt[last] = 1；克隆出的状态cnt初始为 0 - 最终
cnt[u]就是状态u所代表的全部子串的总出现次数（不是单个子串，而是该 endpos 类里最短到最长的所有子串都共享这个值）
查某个具体子串 s 的出现次数？别遍历 SAM，直接走转移边匹配
SAM 本身不支持 O(1) 查任意子串频次；你得先确认 s 是否是原串子串，再拿到它终止的状态，然后取那个状态的 cnt 值。如果匹配中途失配（某步 st[p].next[c] 为空），说明 s 根本不出现在原串中，返回 0。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 从初始状态
0开始，逐字符走next边：p = st[p].next[c]；若某步为 0（未初始化）或 -1（无效索引），立即返回 0 - 走完所有字符后，
p就是代表s的状态（注意：前提是s在 SAM 中有唯一对应状态，而它一定落在某个状态的[minlen, maxlen]区间内） - 此时
cnt[p]就是s的出现次数——但注意：这个值对所有属于同一 endpos 类的子串都一样，所以它确实就是s的出现次数 - 不要试图用
len[p]或minlen去修正，cnt[p]已经是准确的
多次查询子串频次时，预处理 cnt 比每次重跑 DFS 快得多
有人会想：我每次查都从头跑一遍 parent 树 DFS 来算 cnt？不行。构建阶段只做一次拓扑累加，后续所有查询都复用这个 cnt 数组。否则时间复杂度退化成 O(n²)，尤其当查询量大时完全不可接受。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 构建完成后立刻执行一次桶排序 + 逆序累加，得到稳定可用的
cnt[] - 之后所有子串查询都是 O(|s|) 单次匹配，和
cnt无关 - 如果还要支持“长度为 L 的子串最多出现几次”，可以额外维护一个数组
max_cnt[L]：遍历所有状态，对每个状态u，执行max_cnt[st[u].len] = max(max_cnt[st[u].len], cnt[u])，但注意：更长的子串可能被更短的子串包含，所以通常要对max_cnt做后缀最大值处理
cnt[u] 统计的是整个 endpos 类的大小，不是某个特定子串的“独立计数”。很多人卡在这里，以为要对每个子串单独打标记，其实根本不需要——只要状态存在，cnt[u] 就已经包含了它所代表的所有子串的全局出现信息。 
