本文主要是介绍[置顶]AC自动机-算法详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
What's Aho-Corasick automaton?一种多模式串匹配算法，该算法在1975年产生于贝尔实验室，是著名的多模式匹配算法之一。
简单的说，KMP用来在一篇文章中匹配一个模式串；但如果有多个模式串，需要在一篇文章中把出现过的模式串都匹配出来，就需要Aho-Corasick automaton算法了。
My Understanding About Aho-Corasick automaton
我的理解：Aho-Corasick automaton = Trie + KMP
在KMP算法中，匹配单个字符的时候，我们只需要按照文本线性的扫一遍，然后中途失配的时候，next数组会引导k回溯到正确的位置进行下一步的匹配。
但是多个模式串的时候要怎么匹配呢？Trie树不就是一个多模式的匹配吗，如果我们将KMP和Trie数结合起来，是不是会有意想不到的效果呢？
有了这些思考，AC自动机算法就这样产生了。
在AC自动机中，我们首先将每一个模式串插入到Trie树中去，建立一棵Trie树，然后构建fail指针，fail指针，顾名思义，就是当匹配失败的时候，用来引导k回溯的一个插穿在Trie树的各个节点之间的一些指针，就和KMP算法中的next数组是一样的道理。
关于fail指针的构建，推荐看一下李翔大神的PPT。
ppt下载链接：
http://wenku.baidu.com/view/93af2c936bec0975f465e2f1.html
1.构建Trie树
这篇关于[置顶]AC自动机-算法详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
