AC自动机总结（超详细注释）

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;
}