题目 https://cn.vjudge.net/problem/HDU-2222
最简单AC自动机
#include <bits/stdc++.h>using namespace std;
const int MAX = 250001;
const int N = 1000010;const int SIGMA_SIZE = 26;int ch[MAX][SIGMA_SIZE];
int val[MAX],last[MAX],f[MAX],sz;
int ANS;void init()
{sz = 1;memset(ch, 0, sizeof(ch));memset(val, 0, sizeof(val));memset(f, 0, sizeof(f));memset(last, 0, sizeof(last));
}int idx(char c)
{return c - 'a';
}
void add(int u)
{while(u){ANS += val[u];val[u] = 0;u = last[u];}
}
void creat(char *s)
{int u = 0,len = strlen(s);for(int i = 0; i < len; i++){int c = idx(s[i]);if(!ch[u][c]) ch[u][c] = sz++;u = ch[u][c];}val[u]++;
}
void get_fail()
{queue<int> q;for(int i = 0; i < SIGMA_SIZE; i++){if(ch[0][i]) q.push(ch[0][i]);}while(!q.empty()){int r = q.front();q.pop();for(int c = 0;c < SIGMA_SIZE; c++){int u = ch[r][c];if(!u){ch[r][c] = ch[f[r]][c];continue;}q.push(u);int v = f[r];while(v && ch[v][c] == 0) v = f[v];f[u] = ch[v][c];last[u] = val[f[u]] ? f[u] : last[f[u]];}}
}
void find(char *T)
{int len = strlen(T),j = 0;for(int i = 0;i < len; i++){char c = idx(T[i]);j = ch[j][c];if(val[j]) add(j);}
}
char str[N];
int main()
{int T;scanf("%d", &T);while(T--){init();int n;scanf("%d", &n);while(n--){scanf("%s", str);creat(str);}get_fail();scanf("%s", str);ANS = 0;find(str);printf("%d\n",ANS);}return 0;
}