模板题
点亮技能树!!AC自动机!!!!
#include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int max_n = 1e6 + 100; struct AC_Automation { int teir[max_n][27]; int fail[max_n]; int is[max_n]; int cnt = 1; void init() { for (int i = 0;i < max_n;++i)for (int j = 0;j <= 26;++j)teir[i][j] = 0; for (int i = 0;i < max_n;++i)fail[i] = is[i] = 0;cnt = 1; }void insert(char* p) { int cur = 0; int size = strlen(p); for (int i = 0;i < size;++i) { if (teir[cur][p[i] - 'a' + 1]) cur = teir[cur][p[i] - 'a' + 1]; else { teir[cur][p[i] - 'a' + 1] = cnt++; cur = teir[cur][p[i] - 'a' + 1]; } }is[cur]++; }void build() { queue<int> que; for (int i = 1;i <= 26;++i) { if (teir[0][i]) { que.push(teir[0][i]); fail[teir[0][i]] = 0; } }while (!que.empty()) { int u = que.front();que.pop(); for (int i = 1;i <= 26;++i) if (teir[u][i]) { fail[teir[u][i]] = teir[fail[u]][i]; que.push(teir[u][i]); } else teir[u][i] = teir[fail[u]][i]; } }int quiry(char* s) { int size = strlen(s); int cur = 0;int ans = 0; for (int i = 0;i < size;++i) { cur = teir[cur][s[i] - 'a' + 1]; for (int j = cur; j && is[j]; j = fail[j]) { ans += is[j]; is[j] = 0; } }return ans; } }ac; char p[max_n]; char s[max_n]; int main() { ios::sync_with_stdio(0); int T;cin >> T; while (T--) { int n;cin >> n; ac.init(); while (n--) { cin >> p; ac.insert(p); }ac.build(); cin >> s; cout << ac.quiry(s) << endl; } }