找到8号节点的父亲节点的fail节点5号节点，看5号节点有没有为b的子节点。没有，于是再找到5号节点的fail节点2号节点，看2号节点有没有为b的子节点。有，于是8号节点的fail指向4号节点。
这样，一个AC自动机就做好了。
注意到由于辅助节点的存在，我们不需要做任何特判，在树上没有后缀的节点的fail指针会自动连向根节点。
构建fail指针的代码：
void build() { for(int i=0;i<26;++i)ch[0][i]=1; fail[1]=0; queue<int>q; q.push(1); while(!q.empty()) { int x=q.front();q.pop(); for(int i=0;i<26;++i) { int c=ch[x][i]; if(!c)continue; int fa=fail[x]; while(fa&&!ch[fa][i])fa=fail[fa]; fail[c]=ch[fa][i]; q.push(c); } } } 如何利用AC自动机来查找这个问题似乎显而易见，只要根据文本串的内容沿着Trie树的边往下走就行了，一失配就沿着fail边向上跳。
。。。
我在被大佬虐飞之前也是这么想的QwQ
fail边不只是失配指针这么简单，如果你像我刚才说的那么做的话，你就可能会面临下面这样的问题：
为了不让这种事情发生，我们每遇到一个fail指针就必须向上跳到顶，以保证不会漏过任何一个子串，就像这样：
当然，这样未免也太蠢了，于是这里又有一个小优化：如果一个节点的fail指向一个结尾节点，那么这个点也成为一个（伪）结尾节点。在匹配时，如果遇到结尾节点，就进行相应的计数处理。
进行匹配的代码：
void print(int x) { while(x) { if(end[x]) { //计数、打印等等，视题目要求而定 } x=fail[x]; } } void match(char *s) { int len=strlen(s),now=1; for(int i=0;i<len;++i) { int id=s[i]-\'a\'; while(now&&!ch[now][id])now=fail[now]; now=ch[now][id]; if(end[now]||en[now])print(now); //en[now]即为伪结尾标记 } } //记得在build中加上这句话 void build() { ... if(end[fail[c]]||en[fail[c]])en[c]=1; ... } 一个被我们忽略的问题时间复杂度？？？
设模式串平均长度为 $ l $ ，建树复杂度为 $ O(nl) $ ，构建fail指针为 $ O(nl) $ ，匹配时因为每次都要跳fail边，复杂度上界可以达到 $ O(ml) $ ，所以总复杂度为 $ O((n+m)l) $ ！
这和暴力有什么区别(╯°Д°)╯︵┻━┻？？？
虽然说，这个上界应该是十分松的，但是我们想要的是能跑 $ 1e6 $ 的速度！