题目描述
给出n个字符串和一篇文章，求这几个单词在文章中出现过多少个。
思路
多字符串的匹配问题，显然可以用AC自动机做。就先介绍一下AC自动机。AC主要可以包括两个内容：字典树和KMP。
首先我们对所有待匹配的建一棵字典树。
接下来就是匹配时的处理，我们类似KMP，需要处理出一个next数组，表示在当前位置失配后跳转的位置。我们考虑next数组的具体意义：由于匹配是在tried树上进行的，我们假设当前节点为u，代表着字典树上一段字符串的前缀T[1..j]，也就是主串中的S[i-j+1..i]，显然如果能够继续匹配，就继续；否则，我们要找到另一个一字典树上的前缀满足T’[1...k]=S[i-k+1..i]。由此知这个next数组只与字典树本身有关，我们可以直接预处理出这个数组。
考虑如何建立next数组，与KMP类似，假设我们现在有两个节点u、v，并且满足next[u]=v。如果u和v都具有相同的转移边，那么nxt[u的下一个节点]=v下一个节点；而如果转移边不同，我们考虑类似KMP，不断使v=next[v]，知道可以匹配为止。不过我们在建立next数组时可以在假如一个优化：如果不存在ch[u][i]，我们可以直接令ch[u][i]=ch[nxt[u]][i]，这显然是对的，因为不存在使我们也会按next往前跳。
而这道题中还有一点要注意，我们记录的是出现多少单词数，因此匹配完后我们可以“删去”这个节点，即将ed标记设为0。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
char s[1000010];
int ch[MAXN][27],nxt[MAXN],tot,ans,ed[MAXN];
void clear()
{
memset(ch,0,sizeof(ch));
memset(ed,0,sizeof(ed));
tot=1;ans=0;
for(int i=0;i<26;i++)
ch[0][i]=1,ch[1][i]=0;
}
void insert(char *s)
{
int u=1,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(!ch[u][c])ch[u][c]=++tot;
u=ch[u][c];
}
ed[u]++;
}
void bfs()
{
queue<int>q;
for(int i=0;i<26;i++)
ch[0][i]=1;
q.push(1);nxt[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(!ch[u][i])ch[u][i]=ch[nxt[u]][i];
else
{
q.push(ch[u][i]);
int v=nxt[u];
nxt[ch[u][i]]=ch[v][i];
}
}
}
}
void find(char *s)
{
int u=1,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
int k=ch[u][c];
while(k>1)
{
ans+=ed[k];
ed[k]=0;
k=nxt[k];
}
u=ch[u][c];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf(" %s",s);
insert(s);
}
bfs();
scanf(" %s",s);
find(s);
printf("%d\n",ans);
}
return 0;
}