强势 图解 AC自动机（保证您一次就能学会！）

const int N=1000; struct AC_automaton{ 
    int tr[N][26],cnt;//TRIE int e[N];//标记这个结点是不是字符串结尾 int fail[N];//fail指针 void insert(char * s){ 
   }//插入模式串 void build(){ 
   }//构建fail指针 int query(char *t){ 
   }//匹配函数 }; AC_automation ac; 

字典树与字典图

• 关于insert()笔者不做分析，先来看build():

void build(){ 
    queue<int>q; memset(fail,0,sizeof(fail)); for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);//Q1 while(!q.empty()){ 
    int k=q.front();q.pop(); for(int i=0;i<26;i++){ 
    if(tr[k][i]){ 
    fail[tr[k][i]]=tr[fail[k]][i];//Q2 q.push(tr[k][i]); } else tr[k][i]=tr[fail[k]][i];//Q3 } } } 

首先声明了一个队列用于BFS，并清空 $fail$ 数组。

这里的字典树根节点为0，我们将根节点的子节点一一入队。

• Q1-等等，为什么不将根节点入队，非要将它的子节点入队？

然后开始BFS：

• 每次取出队首的结点k。注意，结点k本身的 $fail$ 指针已经求得，我们要求的是k的子节点们的 $fail$ 指针。
• 然后遍历字符集（这里是0-25，对应a-z）：
  • 如果字符i对应的子节点存在，我们就将这个子节点的 $fail$ 指针赋值为 $fail[k]$ 的字符i对应的结点。
  • Q2-不是应该用while循环，不停的跳 $fail$ 指针，判断是否存在字符i对应的结点，然后赋值吗？怎么一句话就完了？
  • 否则，k结点没有字符i对应的子节点，就将 $fail[k]$ 的字符i对应的子节点编号赋值给k
  • Q3-等等，说好的字典树呢？怎么将 $fail[k]$ 的子节点直接赋成k的子节点去了？

这三个Questions构成了 $fail$ 指针构建的精髓。

Q1

• 若将根节点入队，则在第一次BFS的时候，会将根节点的子节点的 $fail$ 指针标记为本身。
• 而将根节点的子节点入队，也不影响算法正确性（因为 $fail$ 指针初始化为0）

Q2&Q3

• Q2与Q3的代码是相辅相成的。
• 简单地来讲，我们将 $fail$ 指针跳转的路径做了压缩（就像并查集的路径压缩），使得本来需要跳很多次 $fail$ 指针变成跳一次。
• 而这个路径压缩的就是Q3的代码在做的事情之一。
• 我们将之前的GIF图改一下：
• 蓝色结点表示BFS遍历到的结点k，深蓝色、黑色的边表示执行完Q3代码连出的字典树的边。
• 可以发现，众多交错的黑色边将字典树变成了字典图。
• 图中省略了连向根节点的黑边（否则会更乱）。
• 我们重点分析一下结点5遍历时的情况：
• 显然，本来应该跳2次才能找到7号结点，但是我们通过10号结点的黑色边直接通过字母s找到了7号结点。
• 因此，Q2结合了Q3的代码，就能在 $O(1)$ 的时间内对单个结点构造 $fail$ 指针。

这就是build完成的两件事：构建 $fail$ 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。

多模式匹配

• 接下来分析匹配函数query():

int query(char *t){ 
    int p=0,res=0; for(int i=0;t[i];i++){ 
    p=tr[p][t[i]-'a'];//Q for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1; } return res; } 

• 声明p作为字典树上当前匹配到的结点，res即返回的答案
• 循环遍历匹配串，p在字典树上跟踪当前字符。
• 利用 $fail$ 指针找出所有匹配的模式串，累加到答案中。然后清0。
• 对 $e[j]$ 取反的操作用来判断 $e[j]$ 是否等于-1。
• Q-读者可能纳闷了：你这里的p一直在往字典树后面走，没有跳 $fail$ 指针啊！这和KMP的思想不一样啊，怎么匹配得出来啊

• Answer to Q

  • 我们从根节点开始尝试匹配ushersheishis，那么p的变化将是：
  • 红色结点表示p结点，粉色箭头表示p在字典图上的跳转，浅蓝色的边表示成功匹配的模式串，深蓝色的结点表示跳 $fail$ 指针时的结点。
  • 其中的部分跳转，我们利用的就是新构建的字典图上的边，它也满足后缀相同（sher和her），所以自动跳转到下一个位置。
  • 综上， $fail$ 指针的意义是，在匹配串同一个位置失配时的跳转指针，这样就利用 $fail$ 指针在同一位置上进行多模式匹配，匹配完了，就在字典图上自动跳转到下一位置。

  总结

  到此，你已经理解了整个AC自动机的内容。我们一句话总结AC自动机的运行原理： 构建字典图实现自动跳转，构建失配指针实现多模式匹配。

  代码

  const int N=1000; struct AC_automaton{ 
        int tr[N][26],cnt;//TRIE int e[N];//标记字符串结尾 int fail[N];//fail指针 void insert(char * s){ 
       //插入模式串 int p=0; for(int i=0;s[i];i++){ 
        int k=s[i]-'a'; if(!tr[p][k])tr[p][k]=++cnt; p=tr[p][k]; } e[p]++; } void build(){ 
        queue<int>q; memset(fail,0,sizeof(fail)); for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]); //首字符入队 //不直接将0入队是为了避免指向自己 while(!q.empty()){ 
        int k=q.front();q.pop();//当前结点 for(int i=0;i<26;i++){ 
        if(tr[k][i]){ 
        fail[tr[k][i]]=tr[fail[k]][i];//构建当前的fail指针 q.push(tr[k][i]);//入队 } else tr[k][i]=tr[fail[k]][i]; //匹配到空字符，则索引到父节点fail指针对应的字符，以供后续指针的构建 //类似并差集的路径压缩，把不存在的tr[k][i]全部指向tr[fail[k]][i] //这句话在后面匹配主串的时候也能帮助跳转 } } } int query(char *t){ 
        int p=0,res=0; for(int i=0;t[i];i++){ 
        p=tr[p][t[i]-'a']; for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1; } return res; } 

  $\%\%\%Sshwy,tql$

  还记得刚才的字典图吗？事实上你并不是一直在往后跳，而是在图上穿梭跳动。比如，刚才的字典图：