%yyb

通俗易懂的ac自动机教程 : https://www.cnblogs.com/cjyyb/p/7196308.html

板子题四道:

开一篇博客存一下板子(第一题ac代码) 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 3;
struct Trie {
    int fail,ch[27],cnt;
}ac[maxn];
int tot=0;
void Insert(char s[])
{
    int len=strlen(s),now=0;
    for(int i=0;i<len;i++) {
        if(!ac[now].ch[s[i]-'a']) ac[now].ch[s[i]-'a']=++tot;
        now=ac[now].ch[s[i]-'a'];
    }
    ac[now].cnt++;
}
void build()
{
    ac[0].fail=0;
    queue<int> q;
    for(int i=0;i<26;i++) if(ac[0].ch[i])   
    {
        ac[ac[0].ch[i]].fail=0; q.push(ac[0].ch[i]);
    }
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int i=0;i<26;i++)
            if(ac[now].ch[i])
            {
                ac[ac[now].ch[i]].fail=ac[ac[now].fail].ch[i];
                q.push(ac[now].ch[i]);
            }
            else ac[now].ch[i]=ac[ac[now].fail].ch[i];
    }
}
int query(char s[])
{
    int len=strlen(s),ans=0,now=0,tmp;
    for(int i=0;i<len;i++) {
        now=ac[now].ch[s[i]-'a'];
        tmp=now;
        while(tmp&&ac[tmp].cnt)
        {
            ans+=ac[tmp].cnt;
            ac[tmp].cnt=0;
            tmp=ac[tmp].fail;
        }
    }
    return ans;
}
int main()
{
    int n;
    char s[maxn];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%s",s);
        Insert(s);
    }
    build();
    scanf("%s",s);
    printf("%d",query(s));
    return 0;
}

第四题代码(第一题改为多组数据需要每次初始化，初始化50*n的大小即可) 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 3;
struct Trie {
    int fail,ch[27],cnt;
}ac[maxn];
int tot=0;
void Insert(char s[])
{
    int len=strlen(s),now=0;
    for(int i=0;i<len;i++) {
        if(!ac[now].ch[s[i]-'a']) ac[now].ch[s[i]-'a']=++tot;
        now=ac[now].ch[s[i]-'a'];
    }
    ac[now].cnt++;
}
void build()
{
    ac[0].fail=0;
    queue<int> q;
    for(int i=0;i<26;i++) if(ac[0].ch[i])    
    {
        ac[ac[0].ch[i]].fail=0; q.push(ac[0].ch[i]);
    }
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int i=0;i<26;i++)
            if(ac[now].ch[i])
            {
                ac[ac[now].ch[i]].fail=ac[ac[now].fail].ch[i];
                q.push(ac[now].ch[i]);
            }
            else ac[now].ch[i]=ac[ac[now].fail].ch[i];
    }
}
int query(char s[])
{
    int len=strlen(s),ans=0,now=0,tmp;
    for(int i=0;i<len;i++) {
        now=ac[now].ch[s[i]-'a'];
        tmp=now;
        while(tmp&&ac[tmp].cnt)
        {
            ans+=ac[tmp].cnt;
            ac[tmp].cnt=0;
            tmp=ac[tmp].fail;
        }
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        char s[maxn];
        scanf("%d",&n);
        for(int i=0;i<=n*50;i++) {
            ac[i].cnt=0;
            for(int j=0;j<26;j++) ac[i].ch[j]=0;
        }
        for(int i=1;i<=n;i++) {
            scanf("%s",s);    
            Insert(s);
        }
        build();    
        scanf("%s",s);
        printf("%d\n",query(s));
    }
    return 0;
}