当然，也有快乐的时候，但那在漫长的人生中也只不过是一瞬间罢了。——《UQ HOLDER！悠久持有者！》

AC自动机

AC自动机用于多模式匹配，集合了 和 的优点，使其可以在 的时间内完成多模式串匹配问题。

假设我们现在有模式串 ，可以构建出如下的字典树：

简直是似曾相识

假设我们现在有文本串“ ”。我们用文本串在 上匹配，却发现从 走不下去了，如果回到根节点重新匹配，评测机肯定是不能接受的，所以我们需要借助 的思想，从 树上的某一点继续开始匹配。

很明显，我们可以从 继续走下去完成匹配，由此我们可以引出失配指针。

失配指针

失配指针 大家都熟，它是字符串界的著名工具人，现在外边打架尽叫它这个名字。

意义

回到我们之前的那棵字典树，对于模式串 中的 ，它的失配指针就是模式串 中的 。

如果一个点 的失配指针指向点 ，那么根到 的字符串就是根到点 的字符串的后缀， 就是 的后缀，而且这个指针的深度要尽量深，打个比方说“ ”的后缀“ ”，这个时候我们就要把失配指针放在 的位置。

插入

这个想必不用多讲，就和正常字典树的插入没啥区别，直接给出代码了：

1
2
3
4
5
6
7
8
9
10
11
12
inline void insert (char* s) // 字典树插入  
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		v = s[i] - 'a';
		if (!trie[u].son[v])
			trie[u].son[v] = ++ cnt; // 记序号而并非字母，序号从 1 开始 
		u = trie[u].son[v];
	}
	trie[u].flag ++;
}

获取

仔细观察可以发现，因为是后缀，所以每一个点 的 指针指向的的深度一定是比 小的。

特别的，第一层的 指针一定指的是 。

根据我们上面说的，如果点 的父亲 的 指针指的是 ，如果 有和 值相同的儿子，那么 的 指针就指向 的儿子，说的比较拗口，但是你画出来就像是一个相似三角形。

代码给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void GetFail () // 获取失配指针  
{
	for (int i = 0; i < 26; i ++)
		trie[0].son[i] = 1; // 开始定义所有子节点为 1 
	Q.push (1);
	trie[1].fail = 0;
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		for (int i = 0; i < 26; i ++)
		{
			int v = trie[u].son[i], Fail = trie[u].fail; // 处理掉子节点的事  
			if (!v) // 如果子节点不存在  
				trie[u].son[i] = trie[Fail].son[i]; // 重新分配子节点为其失配指针的子节点，其实就是复制 
			else
			{
				trie[v].fail = trie[Fail].son[i]; // 直接指就可以了  
				Q.push (v); // 只有实节点才加入队列，自己弄进去的，不算！  
			}
		}
	}
}

教授说现在的字典树是个十分正宗的 ，这似乎确实。

AC自动机的食用

查询

求出失配指针以后就简单很多了，为了避免重复计算，每次经过一个点就给这个点打个标记 ，下一次经过就不重复计算了。

同时，如果一个字符串匹配成功，那么它的 指针也肯定可以匹配成功，于是我们就把 指针再统计一次答案。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int query (char* s)
{
	int u = 1, ans = 0, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a', k = trie[u].son[v];
		while (k > 1 && trie[k].flag != -1)
		{
			ans += trie[k].flag; // 计算有多少个模式串的贡献  
			trie[k].flag = -1; // 标记为走过  
			k = trie[k].fail; // 跳，跳，跳 
		}
		u = trie[u].son[v]; // 跳回去看另一种情况，一种是继续走，一种是在别的模式串上  
	}
	return ans;
}

最后直接给出完整模板题代码（回头检查自己文章的时候发现这里写了个最后，其实不是最后）：

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;

struct Node {
	int son[26], flag, fail;
} trie[N];

int n, cnt = 1;
char s[N];
queue <int> Q;

inline void insert (char* s)
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a';
		if (!trie[u].son[v])
			trie[u].son[v] = ++ cnt;
		u = trie[u].son[v];
	}
	trie[u].flag ++;
}

void GetFail ()
{
	for (int i = 0; i < 26; i ++)
		trie[0].son[i] = 1;
	Q.push (1);
	trie[1].fail = 0;
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		for (int i = 0; i < 26; i ++)
		{
			int v = trie[u].son[i], Fail = trie[u].fail;
			if (!v)
				trie[u].son[i] = trie[Fail].son[i];
			else
			{
				trie[v].fail = trie[Fail].son[i];
				Q.push (v);
			}
		}
	}
}

int query (char* s)
{
	int u = 1, ans = 0, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a', k = trie[u].son[v];
		while (k > 1 && trie[k].flag != -1)
		{
			ans += trie[k].flag;
			trie[k].flag = -1;
			k = trie[k].fail;
		}
		u = trie[u].son[v];
	}
	return ans;
}

int main ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%s", s);
		insert (s);
	}
	GetFail ();
	scanf ("%s", s);
	printf ("%d", query (s));
	return 0;
}

强化

但是上面这个代码是过不了模板题的，所以我们要稍微改一改代码。

题目要求求出出现次数最多的字符串的次数，和这个字符串。

那么就把标记模式串的 改为当前是第几个模式串即可。

1
trie[u].flag = num;

对于查询呢，我们开一个数组 来记录每个字符串出现的次数，然后因为可以重复计算所以不能标为 。

然后如果这是一个模式串的话，就把出现次数加一即可。

完整改动代码如下：

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
106
107
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;

struct Node {
	int son[26], flag, fail;
	void clear () // 全部木大  
	{
		memset (son, 0, sizeof son);
		fail = flag = 0;
	}
} trie[N];

int n, cnt = 1, vis[N], ans;
char s[151][N], q[N];
queue <int> Q;

inline void insert (char* s, int num)
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a';
		if (!trie[u].son[v])
			trie[u].son[v] = ++ cnt;
		u = trie[u].son[v];
	}
	trie[u].flag = num;
}

void GetFail ()
{
	for (int i = 0; i < 26; i ++)
		trie[0].son[i] = 1;
	Q.push (1);
	trie[1].fail = 0;
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		for (int i = 0; i < 26; i ++)
		{
			int v = trie[u].son[i], Fail = trie[u].fail;
			if (!v)
				trie[u].son[i] = trie[Fail].son[i];
			else
			{
				trie[v].fail = trie[Fail].son[i];
				Q.push (v);
			}
		}
	}
}

int query (char* s)
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a', k = trie[u].son[v];
		while (k > 1)
		{
			if (trie[k].flag)
				vis[trie[k].flag] ++;
			k = trie[k].fail;
		}
		u = trie[u].son[v];
	}
	return ans;
}

inline void clear ()
{
	for (int i = 1; i <= cnt; i ++)
		trie[i].clear ();
	for (int i = 1; i <= n; i ++)
		vis[i] = 0;
	cnt = 1, ans = 0;
}

int main ()
{
	while (1)
	{
		scanf ("%d", &n);
		if (!n)
			break;
		clear ();
		for (int i = 1; i <= n; i ++)
		{
			scanf ("%s", s[i]);
			insert (s[i], i);
		}
		scanf ("%s", &q);
		GetFail ();
		query (q);
		for (int i = 1; i <= n; i ++)
			ans = max (ans, vis[i]);
		printf ("%d\n", ans);
		for (int i = 1; i <= n; i ++)
			if (vis[i] == ans)
				printf ("%s\n", s[i]);
	}
	return 0;
}

二次强化

但是上面两个代码是过不了模板题的，所以我们要稍微改一改代码。

这次题目要求求出每个模式串在文本串中出现的次数。

之前我们说 教授说这棵字典树现在变成了一个 ，是因为我们把 指针都想成了有向边。

那么我们可以考虑在遍历到的点打一个标记，最后再一次性把标记上传上来更新其他点的答案，用之前的图来打比方，假设遍历到 的 时，在 的 上打上标记。

到了最后，直接从前者开始跳转 ，然后标记 上传，即点 的 的答案加上点 的答案，这样每个点只经过了一次。

不要回到上面了，那里没有救赎

拓扑优化

因为我们打了标记以后是从深度较大的点更新上去的，所以可以尝试用拓扑排序实现。

使每个点向它的 指针连一条边，很明显，每个点的出度为 ，入度可能有很多，所以不需要建图，直接往 指针跳即可。

指针获取

在这个时候更新 的入度 。

1
2
trie[v].fail = trie[Fail].son[i];
in[trie[v].fail] ++; // 更~新~入~度~当当了当（请用炉石的宣传片最后一段调子唱）

询问

询问的时候就不用暴力跳 了，直接打上标记。

1
2
3
4
5
6
7
8
9
void query (char *s) // 询问  
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		u = trie[u].son[s[i] - 'a'];
		trie[u].ans ++;
	}
}

拓扑

最后直接拓扑，没学的反正我也没写，天王老子都救不了你。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Topulogy () // 拓扑 
{
	for (int i = 1; i <= cnt; i ++)
		if (in[i] == 0)
			Q.push (i);
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		vis[trie[u].flag] = trie[u].ans; // 如果有标记就更新答案 
		int v = trie[u].fail; 
		in[v] --;
		trie[v].ans += trie[u].ans; // 更新 fail 的 ans   
		if (in[v] == 0)
			Q.push (v);
	}
}

最后给出模板代码：

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
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 1;

char s[N], q[N];
int n, cnt = 1, vis[N], ans, in[N], mp[N];

struct Node {
	int son[26], fail, flag, ans;
} trie[N];

queue <int> Q;

inline void insert (char* s, int num)
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		int v = s[i] - 'a';
		if (!trie[u].son[v])
			trie[u].son[v] = ++ cnt;
		u = trie[u].son[v];
	}
	if (!trie[u].flag)
		trie[u].flag = num;
	mp[num] = trie[u].flag;
}

void GetFail ()
{
	for (int i = 0; i < 26; i ++)
		trie[0].son[i] = 1;
	Q.push (1);
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		int Fail = trie[u].fail;
		for (int i = 0; i < 26; i ++)
		{
			int v = trie[u].son[i];
			if (!v)
				trie[u].son[i] = trie[Fail].son[i];
			else
			{
				trie[v].fail = trie[Fail].son[i];
				in[trie[v].fail] ++;
				Q.push (v);
			}
		}
	}
}

void Topulogy ()
{
	for (int i = 1; i <= cnt; i ++)
		if (in[i] == 0)
			Q.push (i);
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		vis[trie[u].flag] = trie[u].ans;
		int v = trie[u].fail;
		in[v] --;
		trie[v].ans += trie[u].ans;
		if (in[v] == 0)
			Q.push (v);
	}
}

void query (char* s)
{
	int u = 1, len = strlen (s);
	for (int i = 0; i < len; i ++)
	{
		u = trie[u].son[s[i] - 'a'];
		trie[u].ans ++;
	}
}

int main ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%s", s);
		insert (s, i);
	}
	GetFail ();
	scanf ("%s", q);
	query (q);
	Topulogy ();
	for (int i = 1; i <= n; i ++)
		printf ("%d\n", vis[mp[i]]);
}

例题

有 个字符串 ， 有一个字符串集合 ，一开始集合是空的。

接下来会发生 个操作，操作有两种形式：

1、 往自己的集合里添加了一个字符串 。

2、 询问 ，集合中有多少个字符串包含 （我们称串 包含串 ，当且仅当 是 的子串）。

什么狗屁题名，脸滚键盘取出来的吗。

什么狗屁时间，不是 的都是人出的吗。

呃……波斯尼亚语翻了一下是“野性”的意思，可这不是克罗地亚信息竞赛吗，啊什么你说搬题搬的主人公名字都不对（这不重要）。

很难判断是在模式串还是文本串来做字典树……但是如果是模式串的话这棵树的形态就会变（因为是动态查询），所以果断选择文本串 。然后对于插入的模式串去做 自动机，然后把这个串在这棵树上的位置到根的链都加一，查询的时候查该字符串在树上的位置就好了。

然后这边又要考虑树上差分，先把所有经过的状态都找出来，然后按 序排序，每次对每个状态单点加，对相邻的 单点减（就是双截棍的情况），最后查询某个点的时候只需要查询子树和即可。

代码如下：

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 100;
const int M = 2e6 + 100;

int head[M], edgecnt, id[N], tree[M], trie[M][26], cnt, root, top[M], hson[M], siz[M], dfsn[M], dfsx, fa[M], dep[M], n, temp[M], len, fail[M]; 

char st[M];

struct Edge {
	int nxt, to;
} edge[M];

inline void add_edge (int u, int v) 
{
	edge[++ edgecnt] = (Edge) {head[u], v};
	head[u] = edgecnt;
}

// Aho-Corasick Automation
 
inline void insert (char st[M], int bh) 
{
	int u = 0, l = strlen (st + 1);
	for (int i = 1; i <= l; i ++)
	{
		int v = st[i] - 'a';
		if (!trie[u][v])
			trie[u][v] = ++ cnt;
		u = trie[u][v];
	}
	id[bh] = u;
}

void GetFail ()
{
	queue <int> Q;
	for (int i = 0; i < 26; i ++)
		if (trie[root][i])
			Q.push (trie[root][i]);
	while (!Q.empty ())
	{
		int u = Q.front ();
		Q.pop ();
		for (int i = 0; i < 26; i ++)
		{
			if (trie[u][i])
			{
				fail[trie[u][i]] = trie[fail[u]][i];
				Q.push (trie[u][i]);
			}
			else
				trie[u][i] = trie[fail[u]][i];
		}  
	}
}

// Heavy Path Decomposition

void Build_Fail_Tree ()
{
	for (int i = 1; i <= cnt; i ++)
		add_edge (fail[i], i);
}

void dfs1 (int x)
{
	dfsn[x] = ++ dfsx;
	siz[x] = 1;
	int maxn = 0;
	for (int i = head[x]; i; i = edge[i].nxt)
	{
		int v = edge[i].to;
		fa[v] = x;
		dep[v] = dep[x] + 1;
		dfs1 (v);
		siz[x] += siz[v];
		if (siz[v] > maxn)
		{
			maxn = siz[v];
			hson[x] = v;
		}
	}
	return;
}

void dfs2 (int x, int topf)
{
	top[x] = topf;
	if (!hson[x])
		return ;
	dfs2 (hson[x], topf);
	for (int i = head[x]; i; i = edge[i].nxt)
	{
		int v = edge[i].to;
		if (v == hson[x])
			continue;
		dfs2 (v, v);
	}
}

int cmp (int a, int b)
{
	return dfsn[a] < dfsn[b];
}

// Lowest Common Ancestors

inline int lca (int x, int y)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
			swap (x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

// Binary Index Tree 

inline int lowbit (int x)
{
	return x & -x;
}

inline void add (int pos, int val)
{
	for (int i = pos; i <= cnt + 1; i += lowbit (i))
		tree[i] += val;
}

inline int query (int pos)
{
	int res = 0;
	for (int i = pos; i; i -= lowbit (i))
		res += tree[i];
	return res;
}

// Main function

int main ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%s", st + 1);
		insert (st, i);
	}
	GetFail ();
	Build_Fail_Tree ();
	dep[0] = 1;
	dfs1 (0);
	dfs2 (0, 0);
	int m, op;
	scanf ("%d", &m);
	while (m --)
	{
		scanf ("%d", &op);
		if (op == 1)
		{
			scanf ("%s", st + 1);
			len = 0;
			int u = 0, l = strlen (st + 1);
			for (int i = 1; i <= l; i ++)
			{
				int v = st[i] - 'a';
				u = trie[u][v];
				temp[++ len] = u;
			}	
			sort (temp + 1, temp + len + 1, cmp);
			len = unique (temp + 1, temp + len + 1) - temp - 1;
			for (int i = 1; i <= len; i ++)
			{
				add (dfsn[temp[i]], 1);
				if (i > 1)
					add (dfsn[lca (temp[i], temp[i - 1])], -1);
			}
		}
		else
		{
			scanf ("%d", &op);
			printf ("%d\n", query (dfsn[id[op]] + siz[id[op]] - 1) - query (dfsn[id[op]] - 1));
		}
	}
	return 0;
}

自动AC机

高度机密
严禁未经授权的人员进行访问
肇事者将被监控、定位并处理
任何未经授权之人员访问文档将立即被模因抹杀触媒处决。
在未接种合适模因疫苗的情況下向下滚动页面将立刻导致心脏骤停死亡。
你已经被警告过了。

本部分只供娱乐，请不要用于大型考试中，如果被告了也不要怪我。

注意，本程序只适用于 这一类评测软件，并不适用于 。

考虑评测的原理，数据被放在 文件夹里，评测软件每次用一个 文件读入到你的程序里，你的程序跑出错误答案到 里，然后评测软件再和 文件夹里的 文件进行比对。

首先来看一下 这个函数：

1
2
freopen ("text.in", "r", stdin);
freopen (const char*, const char*, FILE*) // 这里没写分号是因为这是一个函数哟

前两个都带 号，说明是文件地址的指针。然后因为 文件和你的 文件放在了同一个文件夹里所以可以直接打开，然后现在关键是打开 文件，比如这个 文件可以这么写：

1
freopen ("C:\\Users\\Administrator\\Desktop\\text.cpp\\text\\text.in", "r", stdin);

然后就可以开始写题了，首先还是把正经的数据读进来：

1
2
3
4
5
freopen ("text.in", "r", stdin);
freopen ("text.out", "w", stdout);
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
	scanf ("%d", a[i]);

然后要清楚 文件的命名规则，评测机的文件地址是什么，命名方式是什么。

然后大多数情况我们是不知道的，所以我们需要一个函数 ，需要一个头文件：

1
#include <fstream>

然后来判断你要打开的文件是否存在，否则会导致程序运行的时错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ifstream ifs ("F:\\2021.6.1\\data\\text\\text1.in");
if (ifs.is_open ())
{
	freopen ("F:\\2021.6.1\\data\\text1.in", "r", stdin);
	init ();
	if (check ())
	{
		freopen ("F:\\2021.6.1\\data\\text1.out", "r", stdin);
		string ans;
		cin >> ans;
		cout << ans;
		return 0;
	}
}

建议复制个几遍试试答案格式。

WA自动机

当然要做这个很简单，给出代码：

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>

using namespace std;

int main ()
{
	cout << "NOTTTTTTTHY AK IOI" << endl;
}

TLE自动机

当然要做这个很简单，给出代码：

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
#include <windows.h>

using namespace std;

int main ()
{
	Sleep (60000); // 先睡个一分钟再说 
}