为什么不能用 std::string::find 多次遍历做敏感词过滤
因为时间复杂度太高：对每个敏感词都调用一次 find，平均是 O(n × m)（n 是文本长度，m 是敏感词总数），实际中几十个词就明显卡顿，上百词基本不可用。更糟的是，它无法处理重叠匹配（如“法轮功”和“轮功”同时存在时漏检）或前缀共享（如“杀人”“杀猪”“杀手”重复扫描同一段）。
真正可行的路只有一条：构建一次性预处理结构，让单次扫描完成全部匹配。主流方案就是 AC 自动机（Aho-Corasick），它是多模式字符串匹配的标准解，C++ 标准库不提供，但实现不复杂、性能极好。
AC 自动机核心三步怎么写（C++17 可用）
不是调第三方库，而是手写一个轻量级版本，重点在「建树 + 失败指针 + 匹配」三个环节。以下是最简可用骨架（省略内存管理细节，生产环境建议用 std::unique_ptr）：
struct AcNode {
std::array<AcNode*, 256> children = {};
AcNode* fail = nullptr;
bool is_end = false;
std::vector<std::string_view> patterns; // 存储命中哪些词
};
<p>void insert(AcNode<em> root, std::string_view s) {
auto</em> p = root;
for (char c : s) {
if (!p->children[static_cast<uint8_t>(c)]) {
p->children[static_cast<uint8_t>(c)] = new AcNode();
}
p = p->children[static_cast<uint8_t>(c)];
}
p->is_end = true;
p->patterns.push_back(s);
}</p><p>void build_fail(AcNode<em> root) {
std::queue<AcNode</em>> q;
for (auto<em> child : root->children) {
if (child) {
child->fail = root;
q.push(child);
}
}
while (!q.empty()) {
auto</em> cur = q.front(); q.pop();
for (int i = 0; i < 256; ++i) {
auto<em> next = cur->children[i];
if (!next) continue;
auto</em> f = cur->fail;
while (f && !f->children[i]) f = f->fail;
next->fail = f ? f->children[i] : root;
q.push(next);
}
}
}</p>注意几个实操要点：
立即学习“C++免费学习笔记（深入）”；
-
children用std::array<acnode></acnode>而非std::map<char acnode></char>：避免哈希/红黑树开销，ASCII 场景下空间换时间很值 - 构建
fail指针时，必须用 BFS（队列），不能 DFS；否则父节点的fail还没算好，子节点就依赖它 - 匹配时要沿
fail链向上收集所有is_end == true的节点，否则会漏掉“上海”在“上海市”中作为子串的匹配
如何安全替换或标记敏感词（避免越界和重复）
直接在原字符串上多次 replace 很危险：每次替换后索引偏移，后续匹配位置全错；而且“色情”和“色”共存时，先替换了“色”，“色情”就再也匹配不到了。
正确做法是先扫描得到所有匹配区间（start, end, pattern），再合并/去重，最后批量处理：
- 用
std::vector<:tuple size_t std::string_view>></:tuple>存所有命中区间 - 按
start排序后合并重叠或相邻区间（如“法轮”和“轮功” → “法轮功”） - 从后往前替换（避免索引漂移），或生成新字符串（更安全）
- 若只需检测不替换，直接返回
bool即可，不用存全部 pattern
示例片段（仅检测）：
bool contains_sensitive(const AcNode* root, std::string_view text) {
const AcNode* p = root;
for (size_t i = 0; i < text.size(); ++i) {
uint8_t c = static_cast<uint8_t>(text[i]);
while (p != root && !p->children[c]) {
p = p->fail;
}
p = p->children[c] ? p->children[c] : root;
for (const auto* t = p; t != root; t = t->fail) {
if (t->is_end) return true;
}
}
return false;
}
中文敏感词要额外注意什么
AC 自动机本身不关心编码，但你传入的 std::string_view 必须是 UTF-8 编码的原始字节流，且不能按 char 切分——因为一个汉字占 3 字节，for (char c : s) 会把汉字拆成无效字节，导致匹配失败。
所以必须确保：
- 输入文本和敏感词列表统一为 UTF-8 编码（不是 GBK、UTF-16）
- 插入和匹配时，把整个 UTF-8 字节序列当做一个整体处理，不要尝试“按字符”切分
- 如果业务强制要求按 Unicode 码点匹配（比如屏蔽“?”这种生僻字），就得先用 ICU 或
utf8cpp库做 UTF-8 解码，再喂给 AC 机——但这会显著增加开销，绝大多数场景没必要
真正容易被忽略的是：构建 AC 树前，应对敏感词做标准化（如全角转半角、去除空格、小写归一化），否则“SEX”和“sex”会被当成两个词；但归一化逻辑必须和用户输入文本的处理方式完全一致，否则一定漏匹配。
