AC自动机TLE#1求调
查看原帖
AC自动机TLE#1求调
668906
infinite2021楼主2023/1/17 16:54
#include <bits/stdc++.h>
using namespace std;
const int N=5000010;
int n;
int tr[N][26],cnt[N],idx;
int ne[N],q[N];
char str[N];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!tr[p][u])tr[p][u]=++idx;
        p=tr[p][u];
    }
    cnt[p]++;
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q[++tt]=tr[0][i];
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int c=tr[t][i];
            if(!c)continue;
            int j=ne[t];
            while(j&&!tr[j][i])j=ne[j];
            if(tr[j][i])j=tr[j][i];
            ne[c]=j;
            q[++tt]=c;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",&str);
        insert();
    }
    build();
    scanf("%s",&str);
    int res=0;
    for(int i=0,j=0;str[i];i++)
    {
        int t=str[i]-'a';
        while(j&&!tr[j][t])j=ne[j];
        if(tr[j][t])j=tr[j][t];
        int p=j;
        while(p)
        {
            res+=cnt[p];
            cnt[p]=0;
            p=ne[p];
        }
    }
    printf("%d\n",res);
    return 0;
}

qwq

2023/1/17 16:54
加载中...