一直对AC自动机有种执念，觉得有了它就能自动AC，是一种特别神奇的算法，今天终于见识了。
实际上，学习了AC自动机以后，才发现并没有那么玄乎。
一、Trie（字典树/前缀树）
学习AC自动机前，需要学会字典树。字典树，顾名思义当然是一棵树。特殊地，这棵树上的边是字符。那么对于一条从起点到某一节点的路径，对应了唯一的字符串。这样我们就可以用字典树上的节点来表示字符串。
如图，路径0-1-2-3依次经过“a","b","c"，那么节点3就对应字符串"abc"；同理其它节点也都唯一地对应一个字符串。
观察上图，我们可以发现，
（未完待续）
原文：http://www.cnblogs.com/frank-c1/p/4985105.html