AC自动机

AC自动机=Trie+KMP,是将KMP应用到Trie上的一种数据结构.
AC自动机是一种离线数据结构,一旦构建好fail数组,如果新添加一个字典串,则需要重新构建fail数组.
fail数组:
Trie上的每一个节点,他与Trie树中所有串的最大boarder即为该节点的失配指针.
本质上和KMP算法是相同的,只不过KMP算法是和一个串去匹配,AC自动机是和多个串去匹配.

如何构造AC自动机

1.构建Trie

void insert(int s[])
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'a';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    st[u]=1;
}

2.构建fail指针(bfs、Trie图)

void build()
{
    int hh=0,tt=0;
    for(int i=0;i<26;i++)
        if(tr[0][i])q[tt++]=tr[0][i];
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[hh++]=u;
            }
        }
    }
}

3.查询(有多少字典串在所给串中出现)

int query(char s[])
{
    int res=0; 
    int u=0;
    for(int i=0;s[i];i++)
    {
        u=tr[u][i];
        cnt[u]=1;
    }
    for(int i=idx;i;i--)cnt[fail[q[u]]]|=cnt[q[u]];
    for(int i=0;i<=idx;i++)
        if(st[i])res+=cnt[i];
    return res;
}

题目

1.P5357 【模板】AC 自动机（二次加强版） https://www.acwing.com/solution/content/95424/
2. [CERC2018] The ABCD Murderer https://www.acwing.com/solution/content/95479/
3. 病毒 https://www.acwing.com/solution/content/95540/
4.string https://www.acwing.com/solution/content/95402/
5.文本生成器 https://www.acwing.com/solution/content/95409/
6.数数 https://www.acwing.com/solution/content/95410/
7.[ICPC2019 WF]First of Her Name https://www.acwing.com/solution/content/95544/