aho-corasick自动机可高效统计多模式重叠匹配频次，裸trie因单路径匹配、无后缀链接和无法边扫描边累加，导致o(n²)复杂度且漏匹配。
直接用标准 Trie 节点加计数字段即可，但高频统计场景下必须避免重复遍历、防止漏匹配（如“黑客”和“客”同时存在时，“客”不能因“黑客”已匹配就跳过），核心是「多模式匹配 + 结尾标记 + 后缀链接（fail）」三者结合——也就是 Aho-Corasick 自动机，不是裸字典树。
为什么裸 Trie::search() 无法统计频次
裸字典树的 search() 只能判断“是否存在”，每次调用都从根开始单路径匹配，无法在一次扫描中捕获所有重叠/嵌套敏感词（比如文本 "黑客攻击" 中，“黑客”和“客”若都在词表里，search("黑客") 和 search("客") 需要两次独立扫描，且无法定位“客”在原文中的真实位置）。更严重的是，它不支持边扫描边累加——你得自己切分所有子串去试，时间复杂度退化为 O(n²)。
- 错误做法：
for (int i = 0; i —— 极慢，且 <code>substr频繁分配临时字符串 - 正确前提：所有敏感词已预构建进自动机，文本只需**单次线性扫描**
Aho-Corasick 的 cnt 字段怎么设计才不漏不重
每个节点需存两个整数：end_cnt 表示以该节点结尾的敏感词数量（可 >1，因允许多词同形），total_cnt 表示从根到该节点路径上**所有匹配词的累计频次**（含后缀链上传的）。构建时用 BFS 初始化 fail 指针后，必须做一次「反向传播」：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
queue<trie> q;
q.push(root);
while (!q.empty()) {
Trie* u = q.front(); q.pop();
// 将 fail 节点的 end_cnt 累加到当前 total_cnt
u->total_cnt = u->end_cnt + (u->fail ? u->fail->total_cnt : 0);
for (int i = 0; i children[i]) {
q.push(u->children[i]);
}
}
}</trie>
-
end_cnt在insert()时递增，支持同一词插入多次（如不同权重） -
total_cnt必须在build_fail()后统一计算，不能边走 fail 边加——否则可能重复累加（fail 链有环风险） - 查询时每走到一个节点，直接 +=
u->total_cnt，无需回溯
实际匹配时如何避免 std::string::substr 开销
传入原文用 const char* 或 string_view，内部用下标而非构造子串：
int match(const string& text) {
int res = 0;
Trie* p = root;
for (char c : text) {
int idx = c - 'a';
while (p != root && !p->children[idx]) {
p = p->fail;
}
if (p->children[idx]) {
p = p->children[idx];
}
res += p->total_cnt; // 一次到位，无额外分配
}
return res;
}
- 字符集非英文？把
c - 'a'换成查哈希映射表（如unordered_map<char int> char_to_idx</char>），或改用vector<trie> children</trie>直接索引 Unicode 码点（内存大但快） - 敏感词含中文？libdatrie 更合适，它原生 UTF-8 支持，且双数组结构 cache 局部性好；C++ 手写 AC 自动机处理中文需先 UTF-8 解码为 Unicode code point，再映射，易出错
- 千万级文本？考虑分块处理 +
reserve()避免 vector 动态扩容抖动
真正难的不是建树，而是 fail 指针的传播顺序和 total_cnt 的定义边界——很多人把 total_cnt 错写成「仅当前节点及 fail 节点的 end_cnt 之和」，漏掉了 fail 节点自己的 total_cnt，导致嵌套词（如“密码”和“码”）只算一层。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
