0%

「NOI 2011」阿狸的打字机

首先你需要明白,你不能把每个串都一遍遍插入,复杂度不对。

但是显然,trie树的规模很小。所以我们可以直接边在trie上dfs边插入,代码比较可读:

1
2
3
4
5
6
7
8
9
10
11
void construct(char* s) {
int u = 0;
for (int i = 1; s[i]; ++i) {
if (s[i] >= 'a' && s[i] <= 'z') {
if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot, ff[tr[u][s[i] - 'a']] = u;
u = tr[u][s[i] - 'a'];
}
else if (s[i] == 'B') u = ff[u]; // 撤销一个字符,也就是往父亲跳一格
else if (s[i] == 'P') end_pos[++sz] = u; // 存储每个串的结尾位置
}
}

然后把AC自动机建出来这题就很显然了。

也就是说,X在Y内出现了多少次,等价于在fail树上X的子树内有多少个Y经过的节点。

这个Y经过的节点也可以按dfs的顺序来,进来的时候+1,出去的时候-1,这样就可以离线存询问然后用树状数组维护dfs序就行了。

代码很好理解,只是一开始getfail写错了自闭了半天…

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>

#define test(...) fprintf(stderr, __VA_ARGS__)
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef unsigned int ui;
typedef vector <pair <int, int> > edges;
const int N = 100000 + 10;
int n, m;
char s[N];
int tr[N][26], ff[N], fail[N], tot, end_pos[N], sz, answer[N];
vi g[N];
vector <pii> queries[N];
void construct(char* s) {
int u = 0;
for (int i = 1; s[i]; ++i) {
if (s[i] >= 'a' && s[i] <= 'z') {
if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot, ff[tr[u][s[i] - 'a']] = u;
u = tr[u][s[i] - 'a'];
}
else if (s[i] == 'B') u = ff[u];
else if (s[i] == 'P') end_pos[++sz] = u;
}
}
void get_fail() {
queue <int> q;
for (int i = 0; i < 26; ++i)
if (tr[0][i]) q.push(tr[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
else tr[u][i] = tr[fail[u]][i];
}
}
for (int i = 1; i <= tot; ++i) {
g[fail[i]].push_back(i), g[i].push_back(fail[i]);
}
}
int c[N], L[N], R[N], cc;
void upd(int x, int val) {
for(; x <= cc; x += (x & -x)) c[x] += val;
}
int range(int l, int r) {
int ans = 0;
for (; r; r -= (r & -r)) ans += c[r];
--l;
for (; l; l -= (l & -l)) ans -= c[l];
return ans;
}
void dfs(int u, int pre) {
L[u] = ++cc;
for (int i = 0; i < (int)g[u].size(); i++) if (g[u][i] != pre) dfs(g[u][i], u);
R[u] = cc;
}
void get_ans(char* s) {
int nowsz = 0, u = 0;
for (int i = 1; s[i]; ++i) {
if (s[i] >= 'a' && s[i] <= 'z')
upd(L[tr[u][s[i] - 'a']], 1), u = tr[u][s[i] - 'a'];
else if (s[i] == 'B') {
upd(L[u], -1);
u = ff[u];
} else if (s[i] == 'P') {
++nowsz;
for (int i = 0; i < (int)queries[nowsz].size(); ++i) {
int u = queries[nowsz][i].first, id = queries[nowsz][i].second;
answer[id] = range(L[end_pos[u]], R[end_pos[u]]);
}
}
}
}
void solve() {
scanf ("%s", s + 1);
construct(s);
get_fail();
scanf ("%d", &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf ("%d%d", &x, &y);
queries[y].push_back({x, i});
}
dfs(0, 0);
// dbg(cc); dbg(tot);
get_ans(s);
for (int i = 1; i <= m; ++i)
printf("%d\n", answer[i]);
}

int main() {
#ifdef LOCAL
freopen("sample.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int tests = 1;
while (tests--) solve();
return 0;
}