C++后缀自动机SAM怎么构建并统计子串出现次数-C++-PHP中文网

构建sam必须维护link和len，否则无法正确拓扑转移；link指向最长真后缀状态以支撑parent树计数，len标识该状态最长子串长度，二者在新建/克隆节点时必须显式设置且不可遗漏。

c++后缀自动机sam怎么构建并统计子串出现次数

构建 SAM 时必须维护 `link` 和 `len`，否则无法正确拓扑转移

构建 SAM 的核心是增量插入字符，每个新状态必须记录最长长度 len 和后缀链接 link。漏掉 link 就没法做 parent 树上的计数聚合。常见错误是只存了转移边（next 数组），却没在克隆节点或新建节点时同步设置 link 和 len。

实操建议：

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 对应状态上。

实操建议：

建完 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。

实操建议：

从初始状态 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²)，尤其当查询量大时完全不可接受。

实操建议：

构建完成后立刻执行一次桶排序 + 逆序累加，得到稳定可用的 cnt[]
之后所有子串查询都是 O(|s|) 单次匹配，和 cnt 无关
如果还要支持“长度为 L 的子串最多出现几次”，可以额外维护一个数组 max_cnt[L]：遍历所有状态，对每个状态 u，执行 max_cnt[st[u].len] = max(max_cnt[st[u].len], cnt[u])，但注意：更长的子串可能被更短的子串包含，所以通常要对 max_cnt 做后缀最大值处理