Aho-Corasick 自动机

定义

Aho-Corasick(AC)自动机是 Alfred Aho 与 Margaret Corasick 于 1975 年提出的多模式字符串匹配算法,能在一次文本扫描中同时找出词典里所有关键词的出现位置。

原理

先将全部模式串构建成字典树(Trie),再用广度优先搜索为每个节点计算失配指针(fail 指针),指向当前字符串的最长后缀所对应的节点,类似 KMP 的 next 数组在树上的推广。匹配时沿 Trie 前进,失配则沿 fail 指针跳转,整体复杂度为 O(文本长度 + 模式总长 + 匹配数)。

应用

广泛用于敏感词过滤、入侵检测系统(如 Snort 的规则匹配)、病毒特征码扫描、生物信息序列检索等需要海量关键词批量匹配的场景。

优缺点

匹配阶段与词典大小基本无关,吞吐稳定;缺点是内存占用较高,字符集大时常需数组与哈希混合存储优化。