1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| struct AC_automaton {
int cnt;
int tr[N][26], fail[N], end[N], tot[M];
inline void init() {
cnt = 0;
memset(tr, 0, sizeof tr);
memset(fail, 0, sizeof fail);
memset(end, 0, sizeof end);
memset(tot, 0, sizeof tot);
}
inline void insert(char *s, int x) {
int p = 0, len = strlen(s);
for (int i = 0; i < len; ++i) {
if (!tr[p][s[i]-'a'])
tr[p][s[i]-'a'] = ++cnt;
p = tr[p][s[i]-'a'];
}
end[p] = x;
}
inline void build() {
queue<int> q;
for (int i = 0; i < 26; ++i)
if (tr[0][i])
q.push(tr[0][i]);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (tr[x][i])
fail[tr[x][i]] = tr[fail[x]][i], q.push(tr[x][i]);
else
tr[x][i] = tr[fail[x]][i];
}
}
}
inline void query(char *s) {
int p = 0, len = strlen(s);
for (int i = 0; i < len; ++i) {
p = tr[p][s[i]-'a'];
for (int j = p; j; j = fail[j])
tot[end[j]]++;
}
}
};
|