hdu 2222 Keywords Search（ac自动机模板题，但是有陷阱）

Keywords SearchTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 27477    Accepted Submission(s): 9024


Problem DescriptionInputOutputSample InputSample OutputAuthorRecommend#include <iostream>#include<queue>#include<map>#include<string.h>#include<stdio.h>using namespace std;const int md=500110;const int ssz=26;const int maxn=1000010;char txt[maxn];char words[60];int ch[md][ssz],val[md],f[md],last[md];int sz,ans;void init(){ sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]);}int idx(char c){ return c-'a';}void inser(char *s,int v){ int u=0,n=strlen(s); for(int i=0; i<n; i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof ch[sz]); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]++;//同一单词可以多次计算。。。坑啊。。。}void solve(int j){ if(j) { if(val[j]) { ans+=val[j]; val[j]=0; } solve(last[j]); }}void getf(){ queue<int> q; int u,v,c,r; f[0]=0; for(c=0;c<ssz;c++) { u=ch[0][c]; if(u) { f[u]=0; q.push(u); last[u]=0; } } while(!q.empty())//bfs获取失配数组 { r=q.front(); q.pop(); for(c=0;c<ssz;c++) { u=ch[r][c]; if(!u) { ch[r][c]=ch[f[r]][c];//直接增加失配边 continue; } q.push(u); v=f[r]; while(v&&!ch[v][c]) v=f[v]; f[u]=ch[v][c]; last[u]=val[f[u]]?f[u]:last[f[u]]; } }}void findm(char *T){ int n=strlen(T),c,i,j=0; getf();//获得失配函数 for(i=0;i<n;i++) { c=idx(T[i]); //while(j&&!ch[j][c]) // j=f[j]; j=ch[j][c];//沿着边走就行 if(val[j]) solve(j); else if(last[j]) solve(last[j]); }}int main(){ int i,t,n; scanf("%d",&t); while(t--) { init(); ans=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",words); inser(words,i); } scanf("%s",txt); findm(txt); printf("%d\n",ans); } return 0;}/*1h hhhhh 2 a a a *//*12*/