Trie树与AC自动机专题学习笔记

前置知识

  • KMP算法(之前写的一篇KMP解析博客:传送门
  • Trie树(推荐OI-Wiki上的文章:传送门

AC自动机的定义与实现

定义

AC自动机是基于Trie树的数据结构利用KMP的思想进行多模式匹配的算法。

具体而言,建立一个AC自动机只需要完成两件事

  1. 将所有模式串建立Trie树。
  2. 构建失配指针。

粗略地理解,就是把本来要和原串匹配的一堆模式串合成一棵树,让原串和一棵树去匹配,来获得平均线性的复杂度。

目标

求出每个模式串在原串出现的次数。

匹配流程

个人感觉在KMP的基础下,这个还是很好理解的。如果说让原串和Trie树的每条从root出发到叶子节点的路径进行匹配,那么这个Trie树是毫无意义的。之所以建立Trie树,就是希望利用它的结构去优化多模式匹配。

暴力的做法在匹配成功或匹配失败后,会重新回到根节点,去匹配另外一个模式串,但是类似于KMP,此时我们可以预处理出一个东西,让再次匹配进行移动的时候,可以不移动到根节点,保持一部分的匹配。

举个例子,原串是\(aab\),模式串是\(aa,ab\)两个,在\(aa\)匹配成功后,Trie树事先知道\(aa\)\(ab\)有共同的前缀\(a\),所以就不从根节点开始匹配,而是从\(a\)指向的状态节点开始匹配。

失配指针的含义

对比KMP利用的前缀函数,这里AC自动机利用的是失配指针。

首先,我们要明确失配指针是对于每个状态而言都有一个失配指针。

失配指针的含义从集合的角度更好理解,设集合\(P,Q\)内的每个元素为一个字符串。

\(P\)表示每个模式串的所有前缀字符串构成的集合的并集,例如:对于\("aa","ab","aab"\)\(P=\left\{ "a","b","aa","ab", "aab" \right\}\)

\(Q\)表示从根节点到当前失配状态构成的字符串的所有后缀字符串的集合,例如:对于\("aab"\)\(Q=\left\{"b","ab","aab"\right\}\)

\(P \cap Q\)中选出长度最长的字符串,当前适配状态的失配指针就是这个字符串的最后一个字符指向的状态的编号。

形象一点说,就是通过放弃对一部分前缀的匹配来保证结尾可以继续匹配下去。

文字表述是:指向所有模式串的前缀中匹配当前状态的最长后缀。

失配指针的构建与Trie图

朴素的构造失配指针的方法和KMP构造前缀函数类似,是利用上层状态递推而来的,所以总体上采用宽搜的方式去构建失配指针。

设当前取出的队首元素是\(t\),现在要求该节点的子节点的失配指针,设全部都是小写字母,从0遍历到25。

首先求解前提是存在\(tr[t][i]\)的状态,不存在就直接continue。然后判断\(trie[fail[t],c]\)是否存在,如果存在,就相当于在父节点的最长后缀上加上当前的字符,直接赋值并入队,但是如果不存在,按照失配指针的含义应该需要通过失配指针向上跳转,直到找到存在的状态或跳转至根节点,这是与KMP类似的。

但这样的操作会使AC自动机不能保证稳定线性的时间复杂度,所以,我们对构建部分进行优化。

实际操作是,当不存在\(tr[t][i]\)的状态,我们也进行赋值,\(tr[t][i] = tr[fail[t]][i]\),但宽搜在扩展时仅将实际存在的节点入队并向下搜索。这样做相当于将本来需要一个循环完成的跳转变成了一个赋值,保证了稳定线性的复杂度。

这样操作的正确性在于,如果不存在\(tr[t][i]\)的状态,赋值的操作会有两种结果,一种是\(fail[t]\)对应的状态下有边为\(i\),此时我们就完成了路径压缩,可以继续匹配,第二种是没有这样的边,那么会指向0,即根节点,对整体Trie树并没有造成任何影响,因此这样的操作是正确且高效的。

但是由于对不存在的状态进行赋值,此时的Trie树实际上已经变成了图,因此这样的数据结构被称为Trie图。Trie图是AC自动机的一个优化。

模板题-HDU2222

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, M = 1e6 + 10;
int tr[N][26], fail[N], cnt[N];
char str[M];
int idx = 0;
queue<int> q;
inline void insert()
{
int p = 0;
for (int i = 1; str[i]; i++)
{
int c = str[i] - 'a';
if (!tr[p][c])
tr[p][c] = ++idx;
p = tr[p][c];
}
cnt[p]++;
}

inline void build()
{
for (int i = 0; i < 26; i++)
if (tr[0][i])
q.push(tr[0][i]);
while(!q.empty())
{
int t = q.front();
q.pop();
for(int i = 0; i < 26; i++)
{
if(tr[t][i]) fail[tr[t][i]] = tr[fail[t]][i], q.push(tr[t][i]);
else tr[t][i] = tr[fail[t]][i];
}
}
}

inline int query()
{
int u = 0, res = 0;
for(int i = 1; str[i]; i++)
{
u = tr[u][str[i] - 'a'];
for(int j = u; j; j = fail[j])
res += cnt[j], cnt[j] = 0;
}
return res;
}
int main()
{
int Case;
scanf("%d", &Case);
while (Case--)
{
memset(tr, 0, sizeof tr);
memset(fail, 0, sizeof fail);
memset(cnt, 0, sizeof cnt);
idx = 0;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", str + 1);
insert();
}
build();
scanf("%s", str + 1);
printf("%d\n", query());
}
}

字符串训练赛05题解

POJ1204-Word Puzzles

描述

给定一个字符矩阵和k个字符串,询问字符串在矩阵中出现的起始位置和字符串方向。(可以斜着构成字符串)

题解

和AC自动机的模板相比,文本串变成了字符矩阵,但是实际做题的时候把矩阵转换成字符串去做,但是要注意细节的处理。

  • 利用方向向量分8个方向去匹配
  • 要记录结果可以将模式串反过来构建Trie树,这样匹配到模式串结尾时就是开头的字母。
  • 由于建串的时候时反过来建的,所以我们匹配时候的方向和实际方向是相反的,可以利用数组一一映射一下。

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int M = 1010, N = 1e6 + 10;
char g[M][M], str[M];
int tr[N][26], idx = 0, fail[N], cnt[N], id[N];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int trans[8] = {4, 5, 6, 7, 0, 1, 2, 3};
int n, m, k;
pair<int, int> ans[M];
int dir[M];
inline void insert(int idid)
{
int p = 0;
for (int i = strlen(str) - 1; i >= 0; i--)
{
int c = str[i] - 'A';
if (!tr[p][c])
tr[p][c] = ++idx;
p = tr[p][c];
}
cnt[p]++;
id[p] = idid;
}

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 t = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (tr[t][i])
fail[tr[t][i]] = tr[fail[t]][i], q.push(tr[t][i]);
else
tr[t][i] = tr[fail[t]][i];
}
}
}

inline void query(int x, int y, int co)
{
for (int tx = x, ty = y, j = 0; tx >= 0 && ty >= 0 && tx < n && ty < m; tx += dx[co], ty += dy[co])
{
int p = j = tr[j][g[tx][ty] - 'A'];

while (p)
{
if (cnt[p])
{
int temp = id[p];
ans[temp] = {tx, ty};
dir[temp] = trans[co];
}
cnt[p] = 0;
p = fail[p];
}
}
}

int main()
{

scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
for (int i = 0; i < k; i++)
{
scanf("%s", str);
insert(i);
}
build();

for (int i = 0; i < n; i++)
for (int j = 0; j < 8; j++)
query(i, 0, j), query(i, m - 1, j);
for (int i = 0; i < m; i++)
for (int j = 0; j < 8; j++)
query(0, i, j), query(n - 1, i, j);
for (int i = 0; i < k; i++)
printf("%d %d %c\n", ans[i].first, ans[i].second, dir[i] + 'A');

return 0;
}
----- 本文结束 感谢阅读 -----
0%