AC自动机入门+例题详解

想当年AC自动机算是我ACM路上的一道坎，长长的代码，不知所云的 fail
指针，做题目只有看题解才能过。今天，把AC自动机，重新复习了一遍，发现好多问题都迎刃而解了，这篇博客就总结一下我对AC自动机的认识。

前置知识

Trie字典树(需要借助Trie来存字符串)
KMP(因为fail指针与next数组类似)

简介

AC自动机也是用来处理字符串匹配的问题的。它与KMP不同在，KMP是处理单模式串匹配问题，而AC自动机是用来处理多模式串的问题。例如，给出 n 个单词，再给出一个字符串 S，问有多少个单词在 S 中出现。
不知道有没有同学一开始对AC自动机很好奇，博主我当年看到AC自动机这个名字，还以为是一个学了就能AC好多题的算法，QAQ。

实现方法

把大象关进冰箱有三个步骤 构建一个AC自动机并用于匹配需要三个步骤：

1. 将所有的模式串构建成一棵 Trie 树。
2. 对 Trie 上所有的结点构造前缀指针(失配指针 fail)。
3. 利用前缀指针对主串进行匹配。

接下来，我们一个一个步骤详细来看。
1.建立 Trie 树
这个没有什么好说的，就是按照 Tire 树建立的方法，把所有模式串插入到 Trie 树中，不会的可以看我写的 Trie 树入门 。
代码如下

void insert(char *s)//建Trie树
{
    int rt=1;//初始指针指向根节点 1
    for(int i=0;s[i];++i)
    {
        int c=s[i]-'a';
        if(!ch[rt][c])
        {
            ch[rt][c]=++tot;
        }
        rt=ch[rt][c];
    }
    word[rt]=1;//结尾标记
}

2.建立 fail 数组
fail 指针是类似于KMP里 next 数组存在，我们回顾一下 next 数组有什么用，不就是为了在匹配失败的时候，j 指针跳到 next 数组所指的位置，继续匹配吗，所以我们也可以懂得失配指针 fail 的意义，也是为了在匹配失败的时候，跳到一个合适的位置，而且也是跳到与之最长后缀相同的位置，而且可能会跳到其它分支(因为 Trie 不就是把公共前缀存储到一起了吗)。
接下来，用一个实例描述一下建立 fail 指针的过程。
注：0 为虚拟节点，1 为根节点，字符串只有A,B两个字母组成，实线代表字符指针，虚线代表 fail 指针。

由上例可知，我们需要通过BFS来建立 fail 指针，因为只有BFS才能保证，当前后缀如果之前出现过，就一定能找到。
代码如下(26个字母组成的字符串)

void bfs()//通过BFS建立fail数组
{
    for(int i=0;i<26;++i)//初始0节点全部指向根节点
    ch[0][i]=1;
    que[1]=1;
    fail[1]=0;//若在根节点失配,则无法匹配字符
    for(int q1=1,q2=1;q1<=q2;++q1)
    {
        int u=que[q1];
        for(int i=0;i<26;++i)
        {
            if(!ch[u][i])
            ch[u][i]=ch[fail[u]][i];//优化
            else
            {
                que[++q2]=ch[u][i];//若有这个儿子则将其加入队列中
                int v=fail[u];
                fail[ch[u][i]]=ch[v][i];
            }
        }
    }
}

上面的代码，有一个优化过程，我们在建立 fail 数组的过程中，将当前节点 u 没有的字符指针，指向当前节点失配指针指向的字符指针，这样就可以在查找的过程中节约时间，不必去找第一个满足的字符指针节点。并且在后续建立失配指针的过程中，可以直接 v=fail[u];fail[ch[u][i]]=ch[v][i];因为 ch[v][i] 在之前已经处理好了。
3.主串和模式串的匹配
建立完 fail 指针后，匹配就显得很简单了，这里示例是找主串 S 中，是否有任意模式串 T[i] 的出现，有返回 true，无返回 false。
我们只需要按照字典树的查找方式，如果当前字符串结尾标记为 1，则有模式串，否则如果扫描完主串还未发现，那就是没有。
代码入下

bool find(char *s)//查询主串中是否有任意模式串
{
    int rt=1;
    for(int i=0;s[i];++i)
    {
        int c=s[i]-'a';
        rt=ch[rt][c];
        if(word[rt])
        return true;//匹配到，返回 true
    }
    return false;//没匹配到，返回 false
}

样例分析

Keywords Search(HDU2222)

题目大意
T组数据，每组给定一个 n 个长度不超过 50 的由小写英文字母组成的单词，以及一篇长为 m 的文章，问有多少个单词在文章中出现。
解题思路
这题比模板题要难一些，有许多需要注意的细节。

1. 我们在匹配的时候，不能每次像上面一样，每次直接找当前是不是字符串的结尾。因为，我们是要找数量，而不是仅仅看是否存在。所以，我们需要考虑一种情况，例如单词有 “she”,“he”。我们找到"she"是匹配成功的之后，如果按照之前寻找方式，会把其所有后缀忽略掉，即把"he"忽略了，因此我们需要利用 fail 数组，把当前所有可能后缀全找一遍，看他们是否是字符串结尾。注意，找完一次，要把其标记改掉，防止重复。
2. Trie 数组有 4e7 这么大，如果我们每次都 memset 的话，会超时。我们只需把根节点所以字符指针memset，然后每次产生新节点后，把新节点的字符指针memset即可。

AC代码

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int maxn=5e5+5;
const int maxm=1e6+5;
int ch[maxn][26],fail[maxn];
int que[maxn];//数组模拟队列
char str[maxm];
int tot,T,n;
int word[maxn];
void insert(char *s)//建Trie树
{
    int rt=1;
    for(int i=0;s[i];++i)
    {
        int c=s[i]-'a';
        if(!ch[rt][c])
        {
            ch[rt][c]=++tot;
            memset(ch[tot],0,sizeof(ch[tot]));
        }
        rt=ch[rt][c];
    }
    word[rt]++;
}
void bfs()//通过BFS建立fail数组
{
    for(int i=0;i<26;++i)//初始0节点全部指向根节点
    ch[0][i]=1;
    que[1]=1;
    fail[1]=0;//若在根节点失配,则无法匹配字符
    for(int q1=1,q2=1;q1<=q2;++q1)
    {
        int u=que[q1];
        for(int i=0;i<26;++i)
        {
            if(!ch[u][i])
            ch[u][i]=ch[fail[u]][i];//优化
            else
            {
                que[++q2]=ch[u][i];//若有这个儿子则将其加入队列中
                int v=fail[u];
                fail[ch[u][i]]=ch[v][i];
            }
        }
    }
}
int find(char *s)//查询字符串中有多少单词
{
    int res=0;
    int rt=1,k;
    for(int i=0;s[i];++i)
    {
        int c=s[i]-'a';
        k=ch[rt][c];
        while(k>1)
        {
            res+=word[k];
            word[k]=0;
            k=fail[k];
        }
        rt=ch[rt][c];
    }
    return res;
}
void init()//初始化
{
    tot=1;
    memset(word,0,sizeof(word));
    for(int i=0;i<26;++i)
    ch[1][i]=0;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",str);
            insert(str);
        }
        bfs();
        scanf("%s",str);
        printf("%d\n",find(str));
    }
    return 0;
}