ac自动机学习

模板#includebits/stdc.h using namespace std; const int N500005; struct ac_automation { int trie[N][26]; int e[N]; //字符串的结尾标记 int fail[N]; int L,root; int newnode() //清空该节点下面所有子节点并得到一个新节点 { for(int i0;i26;i) trie[L][i]-1; e[L]0; return L-1; } void init() { L0; rootnewnode(); } void insert(char *s) //结尾节点e数组为1非结尾节点e数组为0 { int proot; for(int i0;s[i];i) { int ks[i]-a; if(trie[p][k]-1)trie[p][k]newnode(); ptrie[p][k]; } e[p]; } void build()// 一个节点的fail节点为,该节点的父节点的fail节点与该节点出边相同的节点 { queueintq; fail[root]root; for(int i0;i26;i) { if(trie[root][i]-1) trie[root][i]root; else { fail[trie[root][i]]root; q.push(trie[root][i]); } } while(!q.empty()) { int kq.front(); q.pop(); for(int i0;i26;i) { if(trie[k][i]-1) { trie[k][i]trie[fail[k]][i]; } else { fail[trie[k][i]]trie[fail[k]][i]; q.push(trie[k][i]); } } } } int query(char *t) { int proot, res0; for(int i0;t[i];i) { ptrie[p][t[i]-a]; for(int jp; j~e[j]; jfail[j])rese[j],e[j]-1; } return res; } }ac; int n; int t; char s[1000010]; int main() { scanf(%d,t); while(t--) { scanf(%d,n); ac.init(); for(int i1;in;i) { scanf(%s,s); ac.insert(s); } ac.build(); scanf(%s,s); printf(%d\n,ac.query(s)); } return 0; }