AC自动机 #10057. 「一本通 2.4 例 1」Keywords Search

给定 个长度不超过 的由小写英文字母组成的单词准备查询，以及一篇长为 的文章，问：文中出现了多少个待查询的单词。多组数据。

输入格式
第一行一个整数 ，表示数据组数；
对于每组数据，第一行一个整数 ，接下去 行表示 个单词，最后一行输入一个字符串，表示文章。

输出格式
对于每组数据，输出一个数，表示文中出现了多少个待查询的单词。

样例
样例输入
1
5
she
he
say
shr
her
yasherhs
样例输出
3

AC自动机的匹配过程分两种情况：(1)当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；(2)当前字符不匹配（与kmp的过程类似），则去当前节点失败指针所指向的字符继续匹配，匹配过程随着指针指向root结束。重复这2个过程中的任意一个，直到模式串走到结尾为止。

简单来说就是没出现过的字母fail指向root，出现过的字母fail指向离root最近的那个字母

听懂直接掌声！！！（下面可以不看）

下面咱们细说
首先root的fail指针指向0，然后root入队，进入循环。第1次循环的时候，我们需要处理2个节点：tree[u]c 和节点s。把这2个节点的失败指针指向root，并且先后进入队列，失败指针的指向对应图-2中的(1)，(2)两条虚线；第2次进入循环后，从队列中先弹出h，接下来h节点的fail指针指向的节点，也就是root；fail[h]也就是0，这时退出循环，并把节点e的fail指针指向root，对应图-2中的(3)，然后节点e进入队列；第3次循环时，现在s是队首，弹出的第一个节点a的操作与上一步操作的节点e相同，把a的fail指针指向root，对应图-2中的(4)，并入队；第4次进入循环时，弹出节点h(图中左边那个)，这时用第二种匹配方式。由于root有h这个儿子节点，图中右边那个，这样便把左边那个h节点的失败指针指向右边那个root的儿子节点h，s是h的父亲节点，root是s的fail指针所指向的节点，右边的h是root的子节点对应图-2中的(5)，然后h入队。以此类推，讲完这个bfs就基本把AC自动机讲完了

if(tree[u][i])第一种情况
{
fail[tree[u][i]]=tree[fail[u]][i];
q.push(tree[u][i]);
}
else 第二种
tree[u][i]=tree[fail[u]][i];
}

图片来源
并对其中注释做出修改

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2 * 1e6 + 9;
int tree[maxn][26];
int word[maxn];
int fail[maxn];
int tot = 0;
typedef long long ll;
void Inserts(string s)
{
    int u=0,i;
    for(i=0;i<s.size();i++)
    {
        int c=s[i]-'a';
        if(!tree[u][c])
        {
            tree[u][c]=++tot;
            memset(tree[tot],0,sizeof(tree[tot]));//清空tot行的元素
        }
        u=tree[u][c];
    }
    word[u]++;
}

void bfs()
{
    queue<int> q;
    int i;
    for(i=0;i<26;i++)
    {
        if(tree[0][i])
        {
            fail[tree[0][i]]=0;
            q.push(tree[0][i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=0;i<26;i++)
        {
            if(tree[u][i])//tree[u][i]是当前节点，u是他的父节点
            {
                fail[tree[u][i]]=tree[fail[u]][i];//让当前节点的失败指针指向其父节点的失败指针指向的节点
                q.push(tree[u][i]);
            }
            else
                tree[u][i]=tree[fail[u]][i];//让当前节点指向其父节点的失败指针指向的节点
            }
    }
}
int query(string s)
{
    int i,j,u=0,ans=0;
    for(i=0;i<s.size();i++)
    {
        int c=s[i]-'a';
        u=tree[u][c];
        for(j=u;j&&word[j]!=-1;j=fail[j])
        {
            ans+=word[j];
            word[j]=-1;
        }
    }
    return ans;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        tot=0;
        memset(word,0,sizeof(word));
        for(int i=0;i<26;i++)
            tree[0][i]=0;
        scanf("%d",&n);
        string s;
        while(n--)
        {
            cin>>s;
            Inserts(s);
        }
        fail[0]=0;
        bfs();
        cin>>s;
        printf("%d\n",query(s));
    }
    return 0;
}