AC自动机板子（from. qwer）

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <iostream> #include <string> #include <queue> using namespace std; const int N=510000; struct Tri { int Next[N][26], fail[N], val[N], root, L; void init() {L = 0;root = newnode();} int newnode() { for(int i = 0;i < 26;i++) Next[L][i] = -1; val[L++] = 0; return L - 1; } void insert(char s[]) { int len = strlen(s), cur = root; for(int i = 0;i < len;i++) { if(Next[cur][s[i]-'a'] == -1) Next[cur][s[i]-'a'] = newnode(); cur = Next[cur][s[i]-'a']; } val[cur]++; } void build() { queue<int>Q; fail[root] = root; for(int i = 0;i < 26;i++) if(Next[root][i] == -1) Next[root][i] = root; else { fail[Next[root][i]] = root; Q.push(Next[root][i]); } while(!Q.empty()) { int cur = Q.front(); Q.pop(); for(int i = 0;i < 26;i++) if(Next[cur][i] == -1) Next[cur][i] = Next[fail[cur]][i]; else { fail[Next[cur][i]]=Next[fail[cur]][i]; Q.push(Next[cur][i]); } } } int query(char s[]) { int len = strlen(s), cur = root, res = 0; for(int i = 0;i < len;i++) { cur = Next[cur][s[i]-'a']; int tmp = cur; while (tmp != root) { res += val[tmp]; val[tmp] = 0; tmp = fail[tmp]; } } return res; } }; char s[N]; Tri AC; int n; int main() { scanf("%d",&n); AC.init(); for(int i = 0;i < n;i++) { scanf("%s",s); AC.insert(s); } AC.build(); scanf("%s",s); printf("%d\n",AC.query(s)); return 0; }