P5357 【模板】AC自动机（二次加强版）

P5357 【模板】AC自动机（二次加强版）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e6+5;
 4 char s[maxn], t[maxn];
 5 int n, cnt, vis[maxn], ans, in[maxn], Map[maxn];
 6 struct node {
 7     int son[26], fail, flag, ans;
 8     void clear() {
 9         memset(son,0,sizeof(son));
10         fail = flag = ans = 0;
11     }
12 }trie[maxn];
13 queue<int> q;
14 void insert(char *s, int num) {
15     int u = 1, len = strlen(s);
16     for (int i = 0; i < len; i++) {
17         int v = s[i]-'a';
18         if (!trie[u].son[v]) trie[u].son[v] = ++cnt;
19         u = trie[u].son[v];
20     }
21     if (!trie[u].flag) trie[u].flag = num;
22     Map[num] = trie[u].flag;
23 }
24 void get_fail() {
25     for (int i = 0; i < 26; i++) trie[0].son[i] = 1;
26     q.push(1);
27     while (!q.empty()) {
28         int u = q.front(); q.pop();
29         int fail = trie[u].fail;
30         for (int i = 0; i < 26; i++) {
31             int v = trie[u].son[i];
32             if (!v) {
33                 trie[u].son[i] = trie[fail].son[i];
34                 continue;
35             }
36             trie[v].fail = trie[fail].son[i];
37             in[trie[v].fail]++;
38             q.push(v);
39         }
40     }
41 }
42 void topu() {
43     for (int i = 1; i <= cnt; i++) {
44         if (in[i] == 0) q.push(i);
45     }
46     while (!q.empty()) {
47         int u = q.front(); q.pop();
48         vis[trie[u].flag] = trie[u].ans;
49         int v = trie[u].fail;
50         in[v]--;
51         trie[v].ans += trie[u].ans;
52         if (in[v] == 0) q.push(v);
53     }
54 }
55 void query(char *s) {
56     int u = 1, len = strlen(s);
57     for (int i = 0; i < len; i++) {
58         u = trie[u].son[s[i]-'a'];
59         trie[u].ans++;
60     }
61 }
62 int main() {
63     scanf("%d",&n); cnt = 1;
64     for (int i = 1; i <= n; i++) {
65         scanf("%s",s);
66         insert(s,i);
67     }
68     get_fail(); scanf("%s",t);
69     query(t); topu();
70     for (int i = 1; i <= n; i++)
71         printf("%d\n",vis[Map[i]]);
72     return 0;
73 }