KMP算法可以在$\mathcal{O}\left(n+m\right)$的时间内高效地完成单个模板串的字符串匹配问题。但是对于多模板串的情况，算法的时间复杂度只有$\mathcal{O}\left(\sum\left(n+m_i\right)\right)$，就不能满足需求了。
这时可以考虑使用AC自动机。
AC自动机的思想很简单，就是用所有模板串建立一颗Trie，并通过BFS对这棵树计算失配函数，匹配时也像KMP一样沿失配边走就行了。时间复杂度降低到$\mathcal{O}\left(n+\sum m_i\right)$，和KMP一样，这也是理论时间复杂度的下界了。
下面给出代码。
构造Trie。
计算失配函数。
进行匹配。
要注意上面的代码没有考虑模板串相同的情况，实际做题时要根据题目要求进行处理。
http://acm.hdu.edu.cn/showproblem.php?pid=2222 代码
一道模板题。
http://poj.org/problem?id=2778 代码
这道是简单的应用，AC自动机可以看成是一个DFA，用矩阵快速幂计算转移方案数即可。
评论 (0)
