AC自动机
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int N=1e4;
const int M=1e6;
const int L=50;
int ch[N*L+50][26],id,cnt[N*L+50];
int ne[N*L+50];
int T,n;
int q[N*L+50];
string w,s;
void insert(string w)
{
int p=0;
for(int i=0;i<w.size();i++)
{
int x=w[i]-'a';
if(ch[p][x]==0)
{
ch[p][x]=++id;
}
p=ch[p][x];
}
cnt[p]++;
}
void bfs()
{
int h=1,t=0;
for(int i=0;i<26;i++)
{
if(ch[0][i])
{
q[++t]=ch[0][i];
}
}
while(h<=t)
{
int f=q[h];
for(int i=0;i<26;i++)
{
if(ch[f][i])
{
int c=ch[f][i];
int j=ne[f];
while(j&&ch[j][i]==0)
{
j=ne[j];
}
if(ch[j][i])
{
j=ch[j][i];
}
ne[c]=j;
q[++t]=c;
}
}
h++;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--)
{
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
memset(ne,0,sizeof(ne));
id=0;
cin>>n;
while(n--)
{
cin>>w;
insert(w);
}
bfs();
cin>>s;
int res=0;
for(int i=0,j=0;s[i]!='\0';i++)
{
int x=s[i]-'a';
while(j&&ch[j][x]==0)
{
j=ne[j];
}
if(ch[j][x])
{
j=ch[j][x];
}
int p=j;
while(p!=0)
{
res+=cnt[p];
cnt[p]=0;
p=ne[p];
}
}
cout<<res<<endl;
}
return 0;
}
Cpp
INFO