最近一直在看AC自动机，打算把它完结了。
首先，我们看到了很多个字符串，自然想到Trie树来存。
例如：
有文本串:ABCDE。
假设一个模板串p在s中出现了，那么它一定的首字母在s中的位置一定是唯一确定的，所以我们可以通过枚举首字母来暴力匹配模板串。
注意：ABC,AB这两个模板串首字母一样，会同时匹配到。
但是这样子太慢了，该怎么优化呢？
参考KMP的思想，我们知道了字符串的前后缀中蕴含了许多有用的信息。
思考过程就不多说，直接给出证明。
做法：设p所有存在于Trie中的后缀的集合是S，那么它的fail指针指向S中最长的元素在Trie中的END节点。
然后，在到了每一个节点时，将它和它的fail，它的fail的fail，……一直到根节点的路径上的点的出现次数全部加1。
当无法继续在Trie树中继续走下去时，跳转到当前节点的fail，然后继续匹配。
现在我们要证明这个做法正确。
我们可以先假设Trie中所有字符串（不管有没有标记，从根出发的任意路径），都是模板串，然后取我们需要的那些即可。
类比上述暴力做法，枚举的是首字母，我们这里按照末字母给一个字符串分类，显然是唯一确定的。
那么，我们在匹配到一个字符串S的时候，它的所有存在的后缀，都会被加一。
于是，它和它的后缀会被统计一次，这其实和暴力是一样的，只是反过来了而已。
那么如果字符串p1和p2不是后缀-母串关系，又该如何呢？
这种情况下，在枚举到p2结束之前，枚举过了p3，于是p1也被统计到了。
这种情况下，直接跳到fail，是可以保证正确的最快的方法。（红线夹的部分相同）
需要注意的是，由于p及其后缀都被加上了一次，跳到fail之后不能直接统计，要走到下一个待匹配的字符才行，不然会重复统计。
走到了下一个待匹配的字符，此时p1和p2的末尾字符不一样，后缀自然也就不一样，所以p2的后缀并不会被重复统计。
也就是说，当出现上述关系的p1，p2时，我们只需要跳到fail就可以统计一个p1。
但是统计要不重复，也就是只能跳转一次，具体哪一次跳转呢？当Trie上无法继续匹配的时候。
也许你也你也可以在倒数第一层跳转，但是这样还要跳回来，非常麻烦。到无法匹配的时候再跳转，就保证了后缀都统计过了，只有情况2。
这样想，一直匹配，匹配到不能匹配为止，已经统计好了包在p里面的所有字符串，只剩下突出去的字符串，这时为了不漏统计，我们要移动尽量少的长度，就是移动到fail了（就算没有交集，特殊情况，会直接跳回根，也是一样的）。