直接用std::string::find过滤敏感词时间复杂度高（o(n×m×k)）、不支持重叠匹配、最长匹配优先及增量扫描；ac自动机通过dfa状态机+fail指针+bfs构建+utf-8正确处理，实现o(n)单次扫描与上下文回调。
为什么不用 std::string::find 做敏感词过滤
直接循环调用 std::string::find 查每个词，时间复杂度是 O(n×m×k)，n 是文本长度，m 是敏感词平均长度，k 是词表大小。10 万字文本 + 500 个敏感词，很容易卡在百毫秒以上，且无法支持「重叠匹配」（如“法轮”和“轮功”需同时命中）或「最长匹配优先」这类业务规则。
更关键的是：它不支持增量扫描——比如日志流、网络包分片到达时，你没法只传入一段新数据就继续上次状态。
DFA 状态机的核心结构怎么建（C++17 实现）
用 std::unordered_map<char size_t></char> 表示每个状态的转移边，配合 std::vector 存所有状态。终态额外标记是否为「输出节点」及对应敏感词索引（支持多词同路径结尾，如“苹果”和“苹果手机”）：
struct DfaState {
std::unordered_map<char size_t> next;
std::vector<size_t> output; // 匹配到的词下标
bool is_fail = false; // 是否为 fail 状态（用于构建 fail 指针）
};
std::vector<dfastate> states(1); // 状态 0 是 root
</dfastate></size_t></char>
插入词时逐字符走当前路径，不存在则新建状态；结尾处往 output push_back 词 ID。注意：中文需按 char 处理会出错——必须先转 UTF-8 字节流再建图，或改用 uint32_t + std::u32string（后者更稳但内存翻倍）。
如何正确构建 AC 自动机的 fail 指针
AC 自动机本质是带 fail 边的 DFA，否则遇到失配就只能回退重试，失去线性性能。构建时用 BFS（不是 DFS），从 root 出发：
- root 的所有子节点的
fail指向 root - 对每个节点 u，遍历其子节点 v（对应字符 c）：若 u 的
fail节点存在边 c 指向 w，则 v 的fail指向 w；否则继续跳fail直到 root 或找到该边 - 合并 output：v->output.insert(end, v->fail->output.begin(), v->fail->output.end()) —— 这步不能漏，否则短词匹配不到
常见坑：fail 指针构建后没做 output 合并；BFS 队列里忘了 push 新建的子节点；用递归模拟 BFS 导致栈溢出（词表大时状态数轻松过万）。
单次扫描如何做到 O(n) 且支持上下文回调
扫描时维护当前状态 ID，每读一个字节（UTF-8 下可能需预解析成 codepoint）就跳转：
size_t state = 0;
for (size_t i = 0; i second : 0;
<pre class="brush:php;toolbar:false;">for (size_t idx : states[state].output) {
callback(idx, i - utf8_len(cp), i); // 传入词ID、起始/结束字节偏移
}}
注意三点：
– utf8_decode 必须返回合法 codepoint，非法字节序列要统一映射为 U+FFFD 或跳过，否则状态机崩；
– fail 回退必须用 while（不是 if），因为 fail 链可能多层；
– 回调函数里不要做耗时操作（如 IO、正则），否则拖慢整个扫描；如需替换，建议只记录 offset+length，批量后处理。
真正难的不是建图，而是把 UTF-8 边界、fail 合并、增量恢复（断点续扫）、内存局部性（std::vector 连续分配比指针树快 3 倍）这几件事全压进一个稳定接口里——多数人栽在 UTF-8 和 fail 合并上，而不是算法本身。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
