洛谷题库 P2414 [NOI2011] 阿狸的打字机 简略题解

洛谷题库 P2414 [NOI2011] 阿狸的打字机

根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。

由自动机的$fail$节点的性质可得，在Fail失配树上，模式串$S_x$的结尾对应的节点下辖的子树上（包括节点$end_{S_x}$），从属于$S_y$在Trie上对应的路径的节点的计数就是该询问的答案。可以通过在Trie上匹配一遍$S_y$后，一遍Fail树上的DFS统计。容易想到的一个优化是采用邻接表以$y$的编号为基准，存储相同的$S_y$对应的模式串$S_{x_1}, S_{x_2}, \dots$，一并计数并统计。

但我们发现，一旦各查询的$S_x, S_y$互异，时间复杂度仍然是恐怖的$\mathrm{O}(\sum{|S_i|} + NM)$（且根据题意，各个串的总长度可以达到$10^9$级别），$M$为查询总数。但我们注意到，在模拟打字机的输入过程以构建/遍历Trie时，每个字符有且仅有$\mathrm{O}(1)$的节点的移动；且对于每一个$x$，我们可以在第一遍遍历构造Trie时记录$S_x$的结尾位置，也就是每个查询对应的根节点。再由上一段提到的性质，可以将一次查询转化为Fail树上在$end_{S_x}$节点子树上的在Trie上处于$S_y$路径上的节点。通过第二遍模拟输入过程遍历时的一些记录，这些处在$S_y$对应的Trie路径上的节点可以被依次标记。

这启发我们结合树的DFS序（DFN），将树的子树划分为DFS序上一段连续的区间；同时我们能够在遍历过程中知道出现在当前状态$S_y$上的节点编号，所以只需要查询该区间内已经过的节点的数量就可以了。更详细地说，每到达/离开一个Trie上的节点，我们都将它在Fail树上的DFN序增加/删除标记；对于每个查询$(S_x, S_y)$，直接查询$end_{S_x}$子树对应的DFN区间的标记的总数即可。于是，满足区间查询、单点更新（在遍历过程中每跳一步就更新节点信息）且常数极小的树状数组已经呼之欲出了。再加上之前提到的，使用链式前向星保存相同文本串$S_y$的查询并一并回答，就可以做到在$\mathrm{O}((|S_0| + M) \log N)$的时间内完成所有查询。

最终我们在$\mathrm{O}(|S_0| + P + (|S_0| + M) \log N)$的时间内完成了本题。R59268096 记录详情

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
105
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
char _s[N], s[N];
int n, m, l, id, x, y, ed[N], pos = -1;
int trie[N][26], cnt, fail[N], e_cnt, head[N];
int qhead[N], ans[N], q_cnt, dfn[N][2], ind = 1;
bool tag[N]; int c[N]; // 树状数组 
queue <int> q;
struct edge {
	int v, nxt;
} e[N];
struct query_ {
	int qid, x, nxt;
} req[N];
void add_q (int x, int y, int qid) {
	req[++q_cnt].x = x, req[q_cnt].nxt = qhead[y], req[q_cnt].qid = qid, qhead[y] = q_cnt;
}
void add_e (int x, int y) {
	e[++e_cnt].nxt = head[x], e[e_cnt].v = y, head[x] = e_cnt;
}

int ask (int x) {
	int res = 0;
	for (; x; x -= x & -x) res += c[x];
	return res;
}
void incre (int x, int y){
	for (; x < N; x += x & -x) c[x] += y;
}

void process (int x) { // 递归遍历构造Trie 
	++pos;
	for (; pos < n; ++pos) {
		switch (_s[pos]) {
			case 'P': ed[++id] = x; break;
			case 'B': return;
			default:
				if (!trie[x][_s[pos] - 'a']) trie[x][_s[pos] - 'a'] = ++cnt;
				process (trie[x][_s[pos] - 'a']);
				break;
		}
	}
	return;
}
void build () { // BFS构建自动机 
	for (int i = 0; i < 26; ++i)
		if (trie[0][i]) {
			q.push (trie[0][i]);
			add_e (0, trie[0][i]);
		}
	int x;
	while (q.size ()) {
		x = q.front (); q.pop ();
		for (int i = 0; i < 26; ++i)
			if (trie[x][i]) {
				fail[trie[x][i]] = trie[fail[x]][i];
				q.push (trie[x][i]);
				add_e (trie[fail[x]][i], trie[x][i]);
			} else trie[x][i] = trie[fail[x]][i];
	}
}
void dfs (int x) { // 求DFN 
	dfn[x][0] = ind;
	for (int i = head[x]; i; i = e[i].nxt)
		++ind, dfs (e[i].v);
	dfn[x][1] = ind;
}
void query (int x) { // 递归遍历并回答查询 
	++pos; int nowx;
	for (; pos < n; ++pos)
		switch (_s[pos]) {
			case 'P': ++id; // 遍历到S[id]的状态 
				for (int i = qhead[id]; i; i = req[i].nxt) // 统一回答关于S[y]的查询 
					ans[req[i].qid] =
						ask (dfn[ed[req[i].x]][1]) - ask (dfn[ed[req[i].x]][0] - 1); // DFN序上的区间查询 
				break;
			case 'B': return;
			default: // 以DFN序更新信息
				nowx = trie[x][_s[pos] - 'a'];
				incre (dfn[nowx][0], 1); // 标记当前点的访问 
				query (nowx, pos);
				incre (dfn[nowx][0], -1); // 取消当前点的标记 
		}
}

int main () {
	/* 洛谷题库 P2414 [NOI2011] 阿狸的打字机 吴秋实 */
	scanf ("%s", _s); n = strlen (_s);
	process (0); // 从根节点递归构建Trie
	build (); // 建立自动机
	dfs (0); // 求出DFN序
	scanf ("%d", &m);
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d", &x, &y);
		add_q (x, y, i); // 链表存储查询 
	}
	id = 0, pos = -1;
	query (0, 0);
	for (int i = 1; i <= m; ++i)
		printf ("%d\n", ans[i]);

	return 0;
}