一、算法简介

AC自动机是在trie树的基础上利用失配指针快速匹配模板串的字符串算法。

其插入模板串复杂度为 O( 模板串长度 )，匹配复杂度为 O( 匹配串长度 )，

在模板串不保证互不相同时退化为 O( 模板串长度 ∗ 匹配串长度 )，可通过优化解决。

二、实现原理

建立trie树之后插入所有模板串，并建立失配指针。

设 i 点的失配指针为 faili​ ,其父节点为 fai​，其元素为 k。

失配指针指向父节点失配指针指向节点的同位子节点，即

faili​=fail(fai​,k)​=(failfai​​,k)

对于以上式子，不妨设父节点已经匹配好，此时子节点若失配即可直接跳跃至下一匹配位置。

在处理完之后直接对文本串暴力跳失配指针并统计。

以上操作复杂度较大，仍有优化空间。

观察AC自动机的实现，不难发现其失配指针由长串向短串覆盖，则短串贡献包含于长串之中。

因此可以考虑建立一棵 fail 树用于处理失配指针，每个串的出现次数即为其终止位置点为根节点的子树和。

三、具体实现

1.插入模板串

直接按照trie树的插入方式指向每一位，并在终点处标记即可。

优化：标记每个模板串的终点

2.建立失配指针

在每个节点上遍历所有直接子节点，并将其失配指针按原理更新即可。

优化：在建立失配指针时连接节点与失配指针所指的节点，即可建出 fail 树。

3.查询

在每一位插入后暴力跳失配指针，处理点上标记。

优化：只对于每个文本串节点计数 +1，在处理完后进行dfs，对每个点统计子树大小，对于每个模板串直接输出其终止节点子树大小即可。

四、复杂度证明：

对于模板串的每个节点最多只会插入一次，因此插入为线性复杂度。

查询时查询文本串每一位，但由于失配指针可能会多次重复，复杂度有可能退化。

优化后每个节点最多扫一遍，具有线性复杂度。

五、应用

在文本串中匹配多模板串等。

六、代码

未优化版本P3808 【模板】AC 自动机（简单版）:

#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=1000005;
int a,b,c,tot=0,head=1,tail=0;
string cmp[MAXN],text;
int node[MAXN][26],nxt[MAXN],cnt[MAXN],fail[MAXN];
int que[MAXN];
inline int read()
{
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
void insert_(string x)
{
    int k=0;
    for(int i=0;i<x.size();++i)
    {
        int now=x[i]-'a';
        if(!node[k][now])node[k][now]=++tot;
        k=node[k][now];
    }
    cnt[k]++;
}
void getfail()
{
    head=1,tail=0;
    for(int i=0;i<26;++i)
        if(node[0][i])que[++tail]=node[0][i];
    while(head<=tail)
    {
        int x=que[head++];
        for(int i=0;i<26;++i)
        {
            int now=i;
            if(node[x][now])
                fail[node[x][now]]=node[fail[x]][now],que[++tail]=node[x][now];
            else node[x][now]=node[fail[x]][now];
        }
    }
}
int get_val(string x)
{
    int ans=0,k=0;
    for(int i=0;i<x.size();++i)
    {
        k=node[k][x[i]-'a'];
        for(int j=k;j&&cnt[j]!=-1;j=fail[j])
            ans+=cnt[j],cnt[j]=-1;
    }
    return ans;
}
signed main()
{
    a=read();
    for(int i=1;i<=a;++i)cin>>cmp[i];
    for(int i=1;i<=a;++i)insert_(cmp[i]);
    cin>>text;
    getfail();
    printf("%d\n",get_val(text));
}

优化版本：P5357 【模板】AC 自动机（二次加强版）

前面的算法以后再来探索吧

#include<iostream>
#include<string>
using namespace std;
const int MAXN=200005;
int a,b,c,tot=0,res=0;
int node[MAXN][26],fail[MAXN];
int que[MAXN],cnt[MAXN],points[MAXN];
int head[MAXN],nxt[MAXN],to[MAXN];
string cmp[MAXN],text;
void add(int x,int y){nxt[++res]=y,to[res]=head[x],head[x]=res;}
inline int read()
{
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
void insert_(string x,int y)
{
    int k=0;
    for(int i=0;i<x.size();++i)
    {
        int j=x[i]-'a';
        if(!node[k][j])node[k][j]=++tot;
        k=node[k][j];
    }
    points[y]=k;
}
void getfail()
{
    int hd=1,tail=0;
    for(int i=0;i<26;++i)
    if(node[0][i])que[++tail]=node[0][i],add(0,node[0][i]);
    while(hd<=tail)
    {
        int x=que[hd++];
        for(int i=0;i<26;++i)
        if(node[x][i])
            fail[node[x][i]]=node[fail[x]][i],que[++tail]=node[x][i],add(fail[node[x][i]],node[x][i]);
        else node[x][i]=node[fail[x]][i];
    }
}
void findx(string x)
{
    int k=0;
    for(int i=0;i<x.size();++i)
        k=node[k][x[i]-'a'],cnt[k]++;
}
void dfs(int x)
{
    for(int i=head[x];i;i=to[i])
    dfs(nxt[i]),cnt[x]+=cnt[nxt[i]];
}
int main()
{
    a=read();
    for(int i=1;i<=a;++i)cin>>cmp[i];
    for(int i=1;i<=a;++i)insert_(cmp[i],i);
    cin>>text;
    getfail();
    findx(text);
    dfs(0);
    for(int i=1;i<=a;++i)printf("%d\n",cnt[points[i]]);
    return 0;
}