<题目链接>
题目大意:
给你一些单词,和一个字符串,问你这个字符串中含有多少个上面的单词。
解题分析:
这是多模匹配问题,如果用KMP的话,对每一个单词,都跑一遍KMP,那么当单词数量非常多的时候,耗时会非常多,所以这里用到了AC自动机,这是一种类似于Trie树的数据结构,但是同时,它也用到了KMP算法中 next数组的思想。
本题可做模板:
#include <bits/stdc++.h>
using namespace std; const int N = 5e5+;
int nxt[N][],cnt[N],fail[N],pos; inline void insert(char *s){
int now=;
for(int i=;s[i];++i){
int to=s[i]-'a';
if(!nxt[now][to])nxt[now][to]=++pos;
now=nxt[now][to];
}
++cnt[now];
}
/*构造失败指针的过程概括起来就一句话:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿
子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到,那就把失败
指针指向root。具体操作起来只需要:先把root加入队列(root的失败指针指向自己或者NULL),这以后我们每处理一个
点,就把它的所有儿子加入队列*/
inline void getFail(){
memset(fail,,sizeof(fail)); //fail指针初始化全部指向根节点
queue<int>q;
for(int i=;i<;++i)
if(nxt[][i])q.push(nxt[][i]);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=;i<;++i){
if(nxt[now][i])q.push(nxt[now][i]),fail[nxt[now][i]]=nxt[fail[now]][i]; //下一个元素的fail指针指向当前元素fail指针指向的元素对应的下一个元素
else nxt[now][i]=nxt[fail[now]][i];
}
}
}
inline int query(char *s){
int now=,res=;
for(int i=;s[i];i++){
int tmp=nxt[now][s[i]-'a'];
while(tmp){
if(cnt[tmp]>=){
res+=cnt[tmp];
cnt[tmp]=-;
}else break;
tmp=fail[tmp];
}
now=nxt[now][s[i]-'a'];
}
return res;
}
char str[int(1e6+)],s[];
int main(){
int T;cin>>T;
while(T--){
pos=;
memset(nxt,,sizeof(nxt));
memset(cnt,,sizeof(cnt));
int n;scanf("%d",&n);
while(n--){
scanf("%s",s);
insert(s); //将模式串插入trie图中
}
getFail();
scanf("%s",str);
printf("%d\n",query(str));
}
}