AC自动机

#include<bits/stdc++.h> using namespace std; const int maxm=1e6+8; const int maxn=1e4+8; struct ha { int nexta[3]; int fail; int num; }trie[maxm]; int Q[maxm]; bool book[maxm]; int tot; int ans; int n,m; char s[maxn]; void insert(char *ch) { int len=strlen(ch); int root=0; int i,j,k; for(i=0;i<len;i++) { int k=ch[i]-'0'; if(!trie[root].nexta[k]) { trie[root].nexta[k]=++tot; } root=trie[root].nexta[k]; } trie[root].num++; } void Pre() { int head=1,tail=1; int root=0; int i,j,k,u; for(i=0;i<=1;i++) { if(trie[root].nexta[i]) { Q[tail++]=trie[root].nexta[i]; } else { trie[root].nexta[i]=0; } } while(head<tail) { u=Q[head++]; for(i=0;i<=1;i++) { if(!trie[u].nexta[i]) { trie[u].nexta[i]=trie[trie[u].fail].nexta[i]; continue; } else { Q[tail++]=trie[u].nexta[i]; int fail=trie[u].fail; trie[trie[u].nexta[i]].fail=trie[fail].nexta[i]; } } } } void AC(char *ch) { int len=strlen(ch); int i,j,k; int root=0; for(i=0;i<len;i++) { j=ch[i]-'0'; root=trie[root].nexta[j]; k=root; while(k) { ans+=trie[k].num; k=trie[k].fail; } } } int main() { while(~scanf("%d",&n)) { ans=0; int a,b,c,d; memset(trie,0,sizeof trie); ans=0; for(a=1;a<=n;a++) { scanf("%s",s); insert(s); } Pre(); scanf("%d",&m); while(m--) { ans=0; scanf("%s",&s); AC(s); printf("%d\n",ans); } } return 0; }