Hdu2222
存一发AC自动机模板…
【代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 500005
#define INF 1LL<<60
using namespace std;
typedef long long ll;
ll read()
{
ll x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)){
if(ch==
'-')f=-
1;ch=getchar();}
while(
isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
int T,n,cnt;
int g[N][
26],Next[N],tag[N];
bool Flag[N];
void Clear(
int x)
{
Next[x]=tag[x]=
0;
memset(g[x],
0,
sizeof(g[x]));
}
void Add(
char *s)
{
int len=
strlen(s);
int now=
0;
for(
int i=
0;i<len;i++)
{
if(!g[now][s[i]-
'a']) {
Clear(++cnt);
g[now][s[i]-
'a']=cnt;
}
now=g[now][s[i]-
'a'];
}
tag[now]++;
}
void Input_Init()
{
n=read();cnt=
0;
Clear(
0);
for(
int i=
1;i<=n;i++)
{
char s[
55];
scanf(
"%s",s);
Add(s);
}
}
void Construct()
{
queue<int>q;
for(
int i=
0;i<
26;i++)
{
int v=g[
0][i];
if(v) q.push(v);
}
while(!q.empty())
{
int k=q.front();q.pop();
for(
int i=
0;i<
26;i++)
{
int &v=g[k][i];
if(v)
{
q.push(v);
Next[v]=k==
0?
0:g[Next[k]][i];
}
else v=k==
0?
0:g[Next[k]][i];
}
}
}
void Solve()
{
char ch[
1000005];
int ans=
0;
scanf(
"%s",ch);
int len=
strlen(ch);
for(
int i=
0,j=
0;i<len;i++)
{
int v=g[j][ch[i]-
'a'];
while(!v&&j)
{
j=Next[j];
v=g[j][ch[i]-
'a'];
}
j=v;
while(v&&tag[v]!=-
1)
{
ans+=tag[v];
tag[v]=-
1;
v=Next[v];
}
}
printf(
"%d\n",ans);
}
int main()
{
T=read();
while(T--)
{
Input_Init();
Construct();
Solve();
}
return 0;
}
