学习了字典树之后，来学一下AC自动机，其实挺简单的，但是很强大
这是一道AC自动机模板题
AC自动机学习博客：ac自动机最详细的讲解，让你一次学会ac自动机。
我的代码：
#include<cstdio>
#include<cstring>
using namespace std;const int maxn=500000+100;int trie[maxn][26],sum[maxn],fail[maxn],tot;
int que[maxn];inline void insert(char* ch){int len=strlen(ch);int root=0;for(int i=0;i<len;i++){int ind=ch[i]-'a';if(!trie[root][ind]) trie[root][ind]=++tot;root=trie[root][ind];}sum[root]++;
}inline void build_fail(){int l=0;int r=1;que[l]=0; // que[l]=root=0while(l<r){int tmp=que[l++];for(int i=0;i<=25;i++){int node=trie[tmp][i];if(node){if(tmp==0){fail[node]=0;}else{int node_tmp=fail[tmp];while(!trie[node_tmp][i] && node_tmp){node_tmp=fail[node_tmp];}if(trie[node_tmp][i]) fail[node]=trie[node_tmp][i];else fail[node]=0;}que[r++]=node;}}}
}inline int search(char* ch){int len=strlen(ch);int root=0;int cnt=0;for(int i=0;i<len;i++){int ind=ch[i]-'a';while(!trie[root][ind] && root) root=fail[root];root=trie[root][ind];if(root){int node_tmp=root;while(node_tmp){if(sum[node_tmp]>=0){cnt+=sum[node_tmp];sum[node_tmp]=-1;}else break;node_tmp=fail[node_tmp];}}}return cnt;
}inline void init(){tot=0;memset(trie,0,sizeof(trie));memset(sum,0,sizeof(sum));memset(fail,0,sizeof(fail));
}char str[maxn*2];int main(){int T,n;scanf("%d",&T);while(T--){init();scanf("%d",&n);getchar();char ch[100];for(int i=1;i<=n;i++){scanf("%s",ch);insert(ch);}build_fail();scanf("%s",str);printf("%d\n",search(str));}
}