hdu2222 发表于 2018-04-30 | 分类于 算法 , 字符串 , AC自动机 | 阅读数 次 链接:hdu2222 题解 ac自动机模板 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<queue>#include<algorithm>#define rint register int #define rep(i,x,y) for(rint i=x;i<=y;++i)#define repd(i,x,y) for(rint i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e6+7;int tr[N][26],End[N],fail[N],cnt,ans,T,n;char a[N];inline void build(char *str,int len){ int now=0; rep(i,1,len){ int k=str[i]-'a'; if(!tr[now][k])tr[now][k]=++cnt; now=tr[now][k]; } End[now]++;}inline void pre(){ queue<int> q; q.push(0); fail[0]=-1; while(!q.empty()){ int k=q.front();q.pop(); rep(i,0,25)if(tr[k][i]){ int son=tr[k][i],p=fail[k]; while(p>=0&&!tr[p][i])p=fail[p]; fail[son]=p>=0?tr[p][i]:0; q.push(son); } }}inline void query(char *str,int len){ int now=0; rep(i,1,len){ int p=now,k=str[i]-'a'; while(p>=0&&!tr[p][k])p=fail[p]; now=p>=0?tr[p][k]:0; int tmp=now; while(tmp){if(End[tmp]>=0)ans+=End[tmp],End[tmp]=-1;else break;tmp=fail[tmp];} }}int main(){ scanf("%d",&T); while(T--){ memset(tr,0,sizeof(tr)); memset(fail,0,sizeof(fail)); memset(End,0,sizeof(End)); scanf("%d",&n);ans=cnt=0; rep(i,1,n){scanf("%s",a+1); build(a,strlen(a+1));} pre(); scanf("%s",a+1); query(a,strlen(a+1)); printf("%d\n",ans); } return 0;}