AC 自动机常用于文本词频统计（本文基础：KMP 算法 - 字符串匹配算法）
前阵子做日志安全审计的一个场景：
关键词库包含很多关键词（如 select、delete），检查日志是否包含关键词从而发现 SQL 注入、XSS 等攻击行为 若采用遍历关键词库逐个在日志中匹配的方案，性能低且算法复杂度会随关键词数增加而变高
那 AC 自动机是怎么做的呢？我找了一个简单例子来说明，若词库为：
{"she", "his", "he", "hers"}将词库变为 Trie 树
root节点不包含字符，除root节点外每个节点都只包含一个字符- 从
root节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
此时可以改为逐位匹配日志来检查是否包含关键词，算法复杂度由日志长度和 Trie 树深度决定（不再与词数直接相关）
在 Trie 树上构造失败指针
通过 Trie 树匹配已经大大降低算法复杂度，不过还可以优化，与 KMP 算法 思路类似：
- 字符串
she的后缀与he的前缀相同，构建she->he的失败指针，同理还有hers->s、his->s、sh->h（黄色虚线） - 其它情况匹配失败后节点指针全指向
root节点（黑色虚线）
AC 自动机工作过程
构建好带失败指针的 Trie 树后，来看看 AC 自动机是如何工作的，以匹配字符串 hishe 为例：
| 读入字符 | 剩余字符串 | 当前位置 | 匹配结果 |
|---|---|---|---|
| hishe | root | ||
| h | ishe | root->h | |
| i | she | h->hi | |
| s | he | hi->his | his |
| h | e | his->s->sh | |
| e | sh->she | she |