今日教练心血来潮让我们学习AC自动机，于是就乖乖开始了学习之旅

然而我连字典树都不会我学啥

dalao原博

luogu模板

首先是

字典树

大概长这样

简单来说每一层都有26个节点对应26个字母，除第一层外

如BANANA这个字符串的和它的后缀的字典树长这样
在存在一整个单词就打标记，查询就顺着一条链往下找

简单来说插入操作就是先找已有的节点，若没有就新增
有就一直顺着链往下找，直到找不到就开辟新节点
图片看yyb博客
以下是建树代码

struct Aho_Corasick_automation//这其实是字典树
{
    int fail;//匹配失败后返回的位置，等同kmp中next数组
    int vis[26];//子节点的位置
    int  End;//标记有几个单词是以这个节点结尾的
}AC[N];

void build(string s)//建立字典树
{
    int l=s.length();
    int now=0;
    for(int i=0;i

AC自动机

简单来说AC自动机是用来解救多个文本串来匹配一个标准串的问题；
首先我们知道只有一个文本串时我们可以用KMP算法快速匹配
但当有非常多的文本串来匹配时一个个比较做KMP就非常吃力了
于是就出现了AC自动机

大家都知道KMP算法是利用next数组来进行优化省去不必要的比对，于是就诞生了fail指针
我接一下yybdalao的图

以这张图，say she shr her构建fail指针

​

通俗一点解释就是当一个文本串与标准串匹配失败后就跳到fail指针继续向下匹配来减少匹配次数，就相当于KMP里面的next
规范一点就是
每次沿着Trie树匹配，匹配到当前位置没有匹配上时，直接跳转到失配指针所指向的位置继续进行匹配。
所以，这个Trie树的失配指针要怎么求？
dalao们的blog告诉我们

Trie树的失配指针是指向：沿着其父节点的失配指针，一直向上，直到找到拥有当前这个字母的子节点的节点的那个子节点
值得一提的是，第二层的所有节点的失配指针，都要直接指向Trie树的根节点。
总之挺玄学，画图理解一下大概是这样。。。

这时候的构造采用bfs
第二层先预处理一下，有节点的就进队，依次往下找存在的节点，然后进队不断往下找

void get_fail()
{
    queue<int>q;
    for(int i=0;i<26;i++)//第二层的fail指针单独预处理
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;//指向根节点
            q.push(AC[0].vis[i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                 //子节点的fail指针指向当前节点的fail指针所指向的节点的相同子节点
                 q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //若不存在,当前节点的这个子节点指向当前节点fail指针的这个子节点
        }
    }
}

完整代码

#include <bits/stdc++.h>

using namespace std;
const int N=1000010;
int n,cnt;

struct Aho_Corasick_automation//这其实是字典树
{
    int fail;//匹配失败后返回的位置，等同kmp中next数组
    int vis[26];//子节点的位置
    int  End;//标记有几个单词是以这个节点结尾的
}AC[N];
void build(string s)//建立字典树
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        if(AC[now].vis[s[i]-'a']==0)AC[now].vis[s[i]-'a']=++cnt;//建立新节点
        now=AC[now].vis[s[i]-'a'];//向下构造节点,从当前节点继续往下找
    }
    AC[now].End+=1;//标记以这个字符结尾
}
void get_fail()
{
    queue<int>q;
    for(int i=0;i<26;i++)//第二层的fail指针单独预处理
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;//指向根节点
            q.push(AC[0].vis[i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                 //子节点的fail指针指向当前节点的fail指针所指向的节点的相同子节点
                 q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //若不存在,当前节点的这个子节点指向当前节点fail指针的这个子节点
        }
    }
}
int AC_query(string s)
{
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i<l;i++)
    {
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t&&AC[t].End!=-1;t=AC[t].fail)
        {
            ans+=AC[t].End;
            AC[t].End=-1;
        }
    }
    return ans;
}
int main()
{
   scanf("%d",&n);
   string s;
   for(int i=1;i<=n;i++)
   {
       cin>>s;
       build(s);

   }
   AC[0].fail=0;
   get_fail();
   cin>>s;
   printf("%d\n",AC_query(s));
    return 0;
}