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

题目链接

https://www.luogu.org/problemnew/show/P3808

AC自动机模板

代码

#include<bits/stdc++.h>
using namespace std;
#define N 1000050
int n;
char s[N];
struct AC_automation
{
    int num,idx[N],ch[N][27],Trie_num;
    int fail[N],end[N];
    void init()
        {for(int i='a';i<='z';i++)idx[i]=++num;}
    void insert(char *s)
        {
            int len=strlen(s),u=0;
            for(int i=0;i<len;i++)
            {
                int x=idx[s[i]];
                if (!ch[u][x])ch[u][x]=++Trie_num;
                u=ch[u][x];
            }
            end[u]++;
        }
    void GetFail()
        {
            queue<int>Q;
            for(int i=1;i<=num;i++)
                if (ch[0][i])Q.push(ch[0][i]);
            while(!Q.empty())
            {
                int u=Q.front();Q.pop();
                for(int i=1;i<=num;i++)
                {
                    if (ch[u][i])fail[ch[u][i]]=ch[fail[u]][i];
                    else {ch[u][i]=ch[fail[u]][i];continue;}
                    Q.push(ch[u][i]);
                }
            }
        }
    void match(char *s)
        {
            int len=strlen(s),u=0,sum=0;
            for(int i=0;i<len;i++)
            {
                int x=idx[s[i]];
                u=ch[u][x];
                for(int t=u;t&&~end[t];t=fail[t])
                    sum+=end[t],end[t]=-1;
            }
            printf("%d
",sum);
        }
}AC;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("aa.in","r",stdin);
#endif
    AC.init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",s),AC.insert(s);
    AC.GetFail();
    scanf("%s",s);
    AC.match(s);
}