AC自动机模板题。
next数组开成char蜜汁mle。。
hdu的tle和mle已经让我不敢相信了。
代码：
#include <bits/stdc++.h> #define totNode 500005 #define maxn 1000006 using namespace std; struct acho { struct st{ int next[26]; int cnt, fail; }st[totNode]; std:: queue<int> Q; int size; int i; void init() { while(Q.empty()==0)Q.pop(); for(int i=0; i<totNode; i++) { memset(st[i].next, 0, sizeof st[i].next); st[i].cnt=st[i].fail=0; } size=0; return; } void insert(char *a) { int now=0; for(i=0; a[i]; i++) { if(st[now].next[a[i]-'a']==0) { st[now].next[a[i]-'a']=++size; } now=st[now].next[a[i]-'a']; } st[now].cnt++; return; } void build() { int now=0; st[0].fail=-1; Q.push(now); int v; while(Q.empty()==0) { int u=Q.front(); Q.pop(); for(i=0; i<26; i++) { if(st[u].next[i]) { if(u==0) { st[st[u].next[i]].fail=0; } else { v=st[u].fail; while(v!=-1 && st[v].next[i]==0)v=st[v].fail; if(v==-1)st[st[u].next[i]].fail=0; else st[st[u].next[i]].fail=st[v].next[i]; } Q.push(st[u].next[i]); } } } return; } int get(int x) { int res=0; int v=x; while(v!=-1) { res+=st[v].cnt; if(st[v].cnt) { st[v].cnt=0; } else break; v=st[v].fail; } return res; } int match(char *a) { int res=0, now=0; for(i=0; a[i]; i++) { if(st[now].next[a[i]-'a']) { now=st[now].next[a[i]-'a']; } else { int v=st[now].fail; while(v!=-1 && st[v].next[a[i]-'a']==0)v=st[v].fail; if(v==-1) { now=0; } else { now=st[v].next[a[i]-'a']; } } if(st[now].cnt) res=res+get(now); } return res; } }acho; char s[maxn]; int main() { int t; cin>>t; while(t--) { int n; scanf("%d", &n); int i; acho.init(); for(i=0; i<n; i++) { scanf("%s", s); acho.insert(s); } acho.build(); scanf("%s", s); printf("%d\n", acho.match(s)); } return 0; }