先看一个问题：给一个很长很长的母串 长度为n，然后给m个小的模式串。求这m个模式串里边有多少个是母串的字串。
最先想到的是暴力O(n*m*len(m)) len(m)表示这m个模式串的平均长度。。。
显然时间复杂度会很高。。。
再改进一些，用kmp让每一模式串与母串进行匹配呢？时间复杂度为O((n + len(m))*m)，还算可以。
可是还有没有更快的算法呢？
编译原理里边有一个很著名的思想：自动机。
这里就要用到确定性有限状态自动机（DFA）。可以对这m个模式串建立一个DFA，然后让母串在DFA上跑，遇到某个模式串的终结节点则表示这个模式串在母串上。
就像这个图，母串“nano”在上边跑就能到达终止节点。
上边说的是自动机的概念。。。还有一个要用到的是trie树，这个不解释了，网上资料一大堆。
这里步入正题：Trie图
trie图是一种DFA，可以由trie树为基础构造出来，对于插入的每个模式串，其插入过程中使用的最后一个节点都作为DFA的一个终止节点。如果要求一个母串包含哪些模式串，以用母串作为DFA的输入，在DFA 上行走，走到终止节点，就意味着匹配了相应的模式串。
ps: AC自动机是Trie的一种实现，也就是说AC自动机是构造Trie图的DFA的一种方法。还有别的构造DFA的方法...
怎么建Trie图？
可以回想一下，在kmp算法中是如何避免母串在匹配过程种指针回溯的？也就是说指针做不必要的前移，浪费时间。
同样的，在trie图中也定义这样一个概念：前缀指针。
这个前缀指针，从根节点沿边到节点p我们可以得到一个字符串S，节点p的前缀指针定义为：指向树中出现过的S的最长的后缀。
构造前缀指针的步骤为：根据深度一一求出每一个节点的前缀指针。对于当前节点，设他的父节点与他的边上的字符为Ch，如果他的父节点的前缀指针所指向的节点的儿子中，有通过Ch字符指向的儿子，那么当前节点的前缀指针指向该儿子节点，否则通过当前节点的父节点的前缀指针所指向点的前缀指针，继续向上查找，直到到达根节点为止。
上图构造出所有节点的前缀指针。
相信原来的问题到这里基本已经解决了。可以再考虑一下它的时间复杂度，设M个串的总长度为LEN