ps：学习AC自动机的时候必须先点亮KMP和字典树的技能点。

步骤：

1.将所有模式串建立一个字典树。

2.对字典树建立失配边。

3.用目标串与字典树进行匹配。

写法：

现在通用的AC自动机写法有两类：1.数组。2.指针。（也有把这两种结合到一起的写法）

指针比较直观，但是做有的题时不好操作；数组相对抽象些，但是适用范围广。我用的是数组的写法，借鉴的是kuangbin大神的板子。

例子：

举个例子，有模式串：she  he  say  shr  her

目标串：yasherhs

现在我们要用这5个模式串建立字典树，并构建失配边。如下图：

代码：（对AC自动机的解释都在代码注释中） 

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <stdlib.h> using namespace std; const int maxn = 500010; struct Trie{ //next存放的是字典树，在上图中是实线，next[i][j]中i是父亲节点，j是孩子节点 //fail存放失配边的信息，在上图中是蓝线 //end标记的是每个模式串末尾节点，在上图中用红色表示 int next[maxn][26],fail[maxn],end[maxn]; int root,L;//root是根节点，L是节点编号 //newnode()创建一个新的节点，并将它的所有孩子节点初始化为-1，返回这个新建节点的编号 int newnode(){ for(int i = 0;i < 26;i++)
            next[L][i] = -1;
        end[L++] = 0; return L-1;
    } //初始化，给根节点初始化为0号节点 void init(){
        L = 0;
        root = newnode();
    } //建立字典树 void insert(char buf[]){ int len = strlen(buf); int now = root;//从根节点开始建立树 for(int i = 0;i <len;i++){ if(next[now][buf[i]-'a'] == -1)//如果现在这个节点下面没有这个节点，就建立新的节点 next[now][buf[i]-'a'] = newnode();
            now = next[now][buf[i]-'a'];//切换到下一个节点 }
        end[now]++;//标记末尾节点 } //建立失配边，用bfs的方式建立 void build(){ queue<int> Q;
         fail[root] = root; for(int i = 0;i < 26;i++){ if(next[root][i] == -1)
                next[root][i] = root; else{
                fail[next[root][i]] = root;//如果没有前缀，就指向root就行了 Q.push(next[root][i]);
            }
         } while(!Q.empty()){ int now = Q.front();
            Q.pop(); for(int i = 0;i < 26;i++){ if(next[now][i] == -1)
                    next[now][i] = next[fail[now]][i]; else{
                    fail[next[now][i]] = next[fail[now]][i];//失配边指向相同前缀 Q.push(next[now][i]);
                }
            }
         }
    } //目标串与字典树进行匹配 int query(char buf[]){ int len = strlen(buf); int now = root; int res = 0; for(int i = 0;i < len;i++){
            now = next[now][buf[i]-'a']; int temp = now; //找目标串中与模式串相同的串 while(temp != root){
                res += end[temp];
                end[temp] = 0;//这里置零是防止重复计数 temp = fail[temp];
            }
        } return res;//返回匹配成功的个数 } //debug函数，不做多解释了 void dubug(){
    }
}; char buf[1000010];
Trie ac; int main() { int t; int n; scanf("%d",&t); while(t--){ scanf("%d",&n);
        ac.init();//初始化 for(int i = 0;i < n;i++){ scanf("%s",buf);
            ac.insert(buf);
        }
        ac.build(); scanf("%s",buf); printf("%d\n",ac.query(buf));
    } return 0;
}