题目:http://acm.hdu.edu.cn/showproblem.php?pid=2222
第一道AC自动机!
T了无数边后终于知道原来它是把若干询问串建一个自动机,把模式串放在上面跑;而且只走模式串的前缀,用 fail 指针来精准遍历每个前缀的每个后缀,就能行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+,K=;
int T,n,c[N][K],fail[N],ed[N],len,ans,tot;
int q[N],he,tl;
char ch[N];
void init()
{
tot=;ans=he=tl=;
memset(c,,sizeof c);memset(fail,,sizeof fail);
memset(ed,,sizeof ed);
}
void insert()
{
int nw=;
for(int i=,d;i<=len;i++)
{
d=ch[i]-'a';
if(!c[nw][d])
c[nw][d]=++tot;
nw=c[nw][d];
}
ed[nw]++;
}
void gtfl()
{
for(int i=;i<;i++)
if(c[][i])
{
q[++tl]=c[][i];
fail[c[][i]]=;
}
while(he<tl)//<
{
int k=q[++he];
for(int i=;i<;i++)
if(c[k][i])
{
q[++tl]=c[k][i];
int nw=fail[k];
while(!c[nw][i]&&nw!=)
nw=fail[nw];
if(!c[nw][i]) fail[c[k][i]]=;
else fail[c[k][i]]=c[nw][i];
}
}
}
void solve()
{
int nw=;
for(int i=,d,cr;i<=len;i++)//只走一遍前缀
{
d=ch[i]-'a';
while(!c[nw][d]&&nw!=) nw=fail[nw];
nw=c[nw][d]; if(!nw) nw=; cr=nw;
while(cr!=&&ed[cr])//遍历该前缀的每个后缀
{
ans+=ed[cr];ed[cr]=;cr=fail[cr];
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",ch+); len=strlen(ch+);
insert();
}
gtfl();
scanf("%s",ch+); len=strlen(ch+);
solve();
printf("%d\n",ans);
}
return ;
}