AC自动机是用来处理多串匹配问题的，即给你很多串，再给你一篇文章，让你在文章中找这些串是否出现过，在哪出现。对于两个字符串匹配问题可用KMP算法，多字符串则用AC自动机。
看下面这个例子：给定5个单词：say she shr he her，然后给定一个字符串yasherhs。问一共有多少单词在这个字符串中出现过。
构造Trie树
首先构造一棵树，如下所示，我们称之为Trie树。
构造失败指针
然后构造失败指针，应当使用BFS算法。失败指针满足下面的性质：
假设有一个节点k，他的失败指针指向j。那么k,j满足：设root到j的距离为n，则从k之上的第n个节点到k所组成的长度为n的单词，与从root到j所组成的单词相同。
即图中红框部分是完全一样的，she中的’e’的失败指针就应该指向her中的’e’。
构造好失败指针如图所示：（为方便递归判断，root的失败指针可指向NULL）
标记终止节点
应当对每个节点都遍历一次所有单词，如果读完某个单词依然可以停留在某个子节点上，则应该将该子节点标记为终止节点。
例如，除了say she shr he her 这5个单词，如果再加入一个单词h，终止节点还应多两个：
匹配过程
一开始，Trie中有指针t1指向root，指针t2指向待匹配串(也就是“文章”)的串头。
接下来的操作和KMP很相似：如果t2指向的字母存在于Trie树中，则t1指向该节点，t2 = t2+1；否则t1顺这当前节点的失败指针向上找，直到t2是t1的一个儿子，或者t1指向NULL（t1指向树根后，t2仍然不是t1的儿子）。
匹配过程中，如果t1路过了一个绿色的节点，那么以这个点结尾的单词就算出现过了。或者如果t1所在的点可以顺着失败指针走到一个绿色点，那么以那个绿点结尾的单词就算出现过了。
Reference
http://hi.baidu.com/lightxianjian/blog/item/d0f0b8de8041125095ee3710.html
http://www.cppblog.com/mythit/archive/2009/04/21/80633.html