AC自动机（字符串多模匹配）

非常经典的一个关于字符串匹配的算法
前置技能是：kmp和trie
重难点是fail指针（其实挺简单的）
其实不一定要会kmp，只要会它的思想就行了。
所谓fail边，其实就是一个失败指针，与kmp的next指针（类似于失败指针，详见我的kmp的博客里的p数组）不同的是，next是对于一个串而言的，而fail则是对全部串都通用，而且是在trie上操作的。
fail[i]表示某一个节点，根节点（以下简称root）到这个节点所组成的字符串，可以完全匹配与i的祖先到i所组成的字符串，这样说有点玄学，给个图深入了解一下吧。

如图，这是一棵trie，然后我们人工脑补它们的fail边。

为什么只连了c，d呢，想想看，root到编号为5的c所构成的串就是“c”，正好符合编号为2的c它自己。
还有root到编号为6的d，构成了“cd”，编号为3的d的祖先到编号为3的d所构成的，也正好是“cd”。
但是有的节点没有匹配怎么办呢，那就直接把fail边连到root就好啦，于是图变成了这样。

ok，现在我们想一想怎么连fail边。
对于一个节点，如果它的fail边不连向root，那么它所连向的节点可能是它父亲的fail所连向的节点的儿子，因为只有在前面都匹配了的情况下，才能去匹配这个节点是否也可以嘛。
为什么是可能呢，因为有可能匹配不了，怎么办呢？那就从它父亲的fail边指向的节点的fail边指向的节点再去找，依次类推，一直到到root为止。
PS：在root这个点也要再匹配一次！root的fail边指向自己。
给出程序了解一下。

        while(h<t)do
        begin
                inc(h);
                for i:=1 to 26 do
                begin
                        if(trie[d[h],i]<>0)then
                        begin
                                inc(t);
                                d[t]:=trie[d[h],i];
                                if(d[h]<>0)then
                                begin
                                        x:=fail[d[h]];
                                        while(trie[x,i]=0)and(x<>0)do x:=fail[x];
                                        //一直去匹配，用它父亲的fail去找
                                        if(trie[x,i]<>0)then
                                        begin
                                                fail[d[t]]:=trie[x,i];
                                                inc(into[trie[x,i]]);
                                                //记录下入度，后面有用的
                                        end;
                                end;
                        end;
                end;
        end;

一定要学会trie先！！！！（不会可以去看我的trie）