AC自动机 P3808 【模板】AC自动机（简单版）（洛谷）

注意：原本是while循环，但通过else解决

fail:爸爸

红色边：fail
黑色边：新增son
绿色边：原本son

query()

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;
const int N=1e6+5;
int n;
string s;
struct node
{
    int son[26];//儿子节点
    int fail;//失配指针，指向的最长后缀的节点下标
    int num;//以此节点为结尾的单词数量
}ac[N];//Trie树(字典树、前缀树)
int cnt=0;//Trie指针

void Insert()
{
    int len=s.size();
    int now=0;//字典树的当前指针,0号点既是根节点，又是空节点
    for(int i=0;i<len;i++)
    {
        if(ac[now].son[s[i]-'a']==0)//若空
            ac[now].son[s[i]-'a']=++cnt;//则构造
        now=ac[now].son[s[i]-'a'];
    }
    ac[now].num+=1;//结尾单词数量加1
}
void get_fail()//找最长后缀  bfs
{
    queue<int> q;
    for(int i=0;i<26;i++)//枚举第二层根节点的所有子节点
    {
        if(ac[0].son[i]!=0)//存在节点
        {
            ac[ac[0].son[i]].fail=0;//指向根节点
            q.push(ac[0].son[i]);//序号，cnt全局变量
        }
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(ac[t].son[i]!=0)//存在这个子节点
            {
                ac[ac[t].son[i]].fail=ac[ac[t].fail].son[i];//我指向爷爷的儿子，即伯父或爸爸（特殊）
                q.push(ac[t].son[i]);
            }
            else//不存在这个子节点
            {
                //原本是while循环，但通过else解决
                ac[t].son[i]=ac[ac[t].fail].son[i];//构造个该节点son
            }
        }
    }
}
int query()
{
    int len=s.size(),now=0,res=0;
    for(int i=0;i<len;i++)
    {
        now=ac[now].son[s[i]-'a'];//通过son向下
        for(int j=now;j&&ac[j].num!=-1;j=ac[j].fail)//通过fail向上回溯
        {
            res+=ac[j].num;//单词有重复
            ac[j].num=-1;//表示加过，以后不再加，此处是验证存不存在。不是存在几次
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    while(n--)
    {
        cin >> s;
        Insert();
    }
    ac[0].fail=0;//0号节点的最长后缀是空，即本身
    get_fail();
    cin >> s;
    cout << query() << endl;
    return 0;
}