不能用std::string::find逐个遍历，因其时间复杂度O(N×M)高、无法处理重叠匹配和最长前缀优先；AC自动机可实现O(L+Z)高效匹配，并支持中文UTF-8及掩码安全替换。
敏感词匹配为什么不能用 std::string::find 逐个遍历？
因为时间复杂度太高：假设有 N 个敏感词、文本长度为 M，暴力遍历平均是 O(N×M)，实际业务中（比如弹幕过滤、评论审核）可能要处理上万词库 + 实时高并发，std::string::find 会立刻成为瓶颈。更关键的是它无法处理“重叠匹配”和“最长前缀优先”等真实需求——比如词库含 "色情" 和 "色"，输入 "色情人流"，只用 find 很容易漏掉前者或重复替换。
用 Aho-Corasick 自动机实现 O(L + Z) 匹配
Aho-Corasick（AC 自动机）是业界通用解法，构建一次后，扫描文本只需 O(L) 时间（L 是文本长度），同时输出所有匹配位置和对应敏感词，Z 是匹配总数。C++ 没有标准库实现，但可用 std::vector + std::array 手写轻量版（无需第三方库）：
struct ACAutomaton {
static constexpr int CHARSET_SIZE = 256;
struct Node {
int fail = 0;
int output = -1; // 词索引，-1 表示无词
std::array<int, CHARSET_SIZE> next{};
};
std::vector<Node> nodes{1}; // root at index 0
<pre class='brush:php;toolbar:false;'>void insert(const std::string& word, int idx) {
int u = 0;
for (unsigned char c : word) {
if (!nodes[u].next[c]) {
nodes[u].next[c] = nodes.size();
nodes.emplace_back();
}
u = nodes[u].next[c];
}
nodes[u].output = idx;
}
void build() {
std::queue<int> q;
for (int c = 0; c < CHARSET_SIZE; ++c) {
if (nodes[0].next[c]) {
q.push(nodes[0].next[c]);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < CHARSET_SIZE; ++c) {
int& v = nodes[u].next[c];
if (!v) continue;
int f = nodes[u].fail;
while (f && !nodes[f].next[c]) f = nodes[f].fail;
nodes[v].fail = nodes[f].next[c] ? nodes[f].next[c] : 0;
nodes[v].output = nodes[nodes[v].fail].output != -1
? nodes[nodes[v].fail].output : nodes[v].output;
q.push(v);
}
}
}
std::vector<std::tuple<int, int, int>> search(const std::string& s) {
std::vector<std::tuple<int, int, int>> res; // {start, end, word_idx}
int u = 0;
for (int i = 0; i < s.size(); ++i) {
unsigned char c = s[i];
while (u && !nodes[u].next[c]) u = nodes[u].fail;
u = nodes[u].next[c] ? nodes[u].next[c] : 0;
int t = u;
while (t && nodes[t].output != -1) {
res.emplace_back(i - (int)word_list[nodes[t].output].size() + 1, i, nodes[t].output);
t = nodes[t].fail;
}
}
return res;
}
std::vector<std::string> word_list;};
注意点：
立即学习“C++免费学习笔记（深入）”；
-
insert()中必须用unsigned char索引next数组，否则中文 UTF-8 字节（如0xE8）会被解释为负数导致越界 -
build()中 fail 边构造必须用 while 循环跳转，不能只跳一层——否则像"ab"、"b"这类词会漏匹配 -
search()内部的 while 循环必须沿 fail 链向上收集所有 output，否则无法支持“多词共用后缀”的情况（如"黑客"和"客"）
掩码替换时如何避免重复覆盖和越界？
直接按匹配结果顺序替换字符串会导致位置偏移（比如把第 2–4 字符替成 "***"，后面所有匹配起始坐标就全乱了）。正确做法是先收集全部匹配区间，再从后往前替换：
步骤：
- 调用
search()得到所有{start, end, word_idx}元组 - 按
end降序排序（确保长词优先，且后段替换不影响前段坐标） - 对每个匹配，用
s.replace(start, end - start + 1, "***")—— 注意replace的第二个参数是长度，不是 end 坐标
如果需要保留原始词长度（如替成等长 "*"），得提前缓存原词长度：std::string mask(word.size(), '*')，再 s.replace(start, len, mask)。
中文场景下 AC 自动机的编码与性能取舍
AC 自动机默认按字节建树，对 UTF-8 编码的中文完全可用，但要注意：
- 不要对字符串做任何
std::wstring或std::codecvt_utf8转换——这会引入额外开销且易出错；直接操作std::string的 raw bytes 即可 - 词库若含 emoji 或生僻汉字（4 字节 UTF-8），仍能正常工作，因为 AC 树节点是按单字节索引的，无需修改逻辑
- 内存占用主要来自
nodes向量，每个节点固定 256×4 字节（约 1KB），10 万词典型占用在 50–200MB，远低于哈希表暴力方案的内存碎片和 cache miss
真正卡顿的地方往往不是匹配本身，而是词库加载和 AC 树构建——建议在服务启动时一次性完成，运行时只调用 search()。
