AC 自动机
KMP 自动机¶
为了介绍 AC 自动机这种神奇的算法，先介绍自动机和 KMP 自动机
有限状态自动机 (DFA)：字符集，有限状态控制，初始状态，接受状态
KMP 自动机：一个不断读入待匹配串，每次匹配时走到接受状态的 DFA
共有 个状态，第 个状态表示已经匹配了前 个字符
（约定 ）
我们发现 只依赖于之前的值，所以可以跟KMP一起求出来
时间和空间复杂度：
一些细节：走到接受状态之后立即转移到该状态的
AC 算法就是 Trie 上的自动机¶
注意在BFS的同时求出 即可
可以解决多串匹配问题
注意细节： 还是
前者能找到每次匹配，后者只能求出匹配次数（通过合并接受状态）
AC 自动机的实现¶
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用