直接用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
插入词时逐字符走当前路径，不存在则新建状态；结尾处往 output push_back 词 ID。注意：中文需按 char 处理会出错——必须先转 UTF-8 字节流再建图，或改用 uint32_t + std::u32string（后者更稳但内存翻倍）。
如何正确构建 AC 自动机的 fail 指针
AC 自动机本质是带 fail 边的 DFA，否则遇到失配就只能回退重试，失去线性性能。构建时用 BFS（不是 DFS），从 root 出发：
立即学习“C++免费学习笔记（深入）”；
- 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 < text.size(); ) {
uint32_t cp = utf8_decode(text, i); // 自行实现或用 ICU
while (state != 0 && states[state].next.find(cp) == states[state].next.end()) {
state = states[state].fail;
}
auto it = states[state].next.find(cp);
state = (it != states[state].next.end()) ? it->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 合并上，而不是算法本身。
