一个最简单的字符串匹配问题可以理解为如下：
给定一个长度为 n 的字符串 \(s\)，检测长度为 m 的字符串 \(t\) 在 \(s\) 中出现的位置。
最开始，我们可以使用一些比较朴素的做法，例如直接枚举 \(t\) 在 \(s\)
中的位置，通过对每个位置进行比较进而得到答案，这样做的最差时间复杂度为
\(O(n*m)\)。当字符串长度较长时，时间代价过大。
事实上我们可以思考，在每次匹配失败后朴素的做法是将字符串 \(t\)
向后移动一位继续重新匹配。是否存在一种方法可以减少重新匹配的次数呢？也就是说每次向后移动一位是否增加了很多不必要的匹配呢？
最长公共真前后缀！每次匹配失败后并不是只移动一位，而是移动到当前子串的最长公共真前后缀的位置，这样就避免了一部分的重复匹配，KMP
算法正是这样做的。它的基本思路是首先对字符串 \(t\) 进行预处理数组 \(next\)，计算出其前缀子串的最长公共真前后缀长度，这样就可以在匹配过程中进行转移。具体实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> prefix_function(string t) {
int n = t.length();
vector<int> next(n);
for (int i = 1; i < n; i++) {
int j = next[i - 1];
while (j > 0 && t[i] != t[j]) {
j = next[j - 1];
}
if (t[i] == t[j]) {
j++;
}
next[i] = j;
}
return next;
}
|
经过 prefix_function 我们就可以得到预期的 \(next\)
数组，那我们该怎么使用呢？一般只有在匹配失效时使用 \(next\) 数组，这时只需要将字符串 \(t\)
的指针指向上一个匹配的公共真前后缀后的位置即可，具体实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| vector<pair<int, int>> KMP(string s, string t) {
int i = 0, j = 0;
vector<int> next = prefix_function(t);
vector<pair<int, int>> ans;
while (i < s.length()) {
if (s[i] == t[j]) {
i++, j++;
if (j == t.length()) {
ans.emplace_back(make_pair(i - j, i - 1));
j = next[j - 1];
}
}
else {
if (j > 0) {
j = next[j - 1];
}
else {
i++;
}
}
}
return ans;
}
|
以上代码返回的是所有在主串 \(s\)
中出现 \(t\) 的开始结束下标。
那么问题又来了，当我们想在一个字符串里寻找多个这样的 \(t\) 时该怎么做呢？对每一个 \(t\) 都构建 \(next\)
数组吗？这听起来是可行的，算了算时间复杂度也不过 \(O((n + m)*m)\)，似乎是可以接受的。
有没有更好的做法呢？这若干个字符串 \(t\)
会不会有联系？能不能只用线性时间复杂度完成这样的工作呢？
AC
自动机正是为了这种解决这种多模式匹配问题而出现的，具体的思路是
Trie tree + fail pointer。要明白的一点是字典树(Trie
tree)本质上就是一个自动机，这个自动机只能接受且仅接受指定的字符串集合中的元素，而且是通过不同的字母形成的边进行转移。
我们首先利用这些字符串 \(t\)
构建一棵字典树。显然光这样是不够的，当我们用主串去输入到这个字典树的时候，会有一些异常情况，比如有些字母不存在边对他们进行转移，这时候就需要加点东西：fail
指针。
fail
指针的作用是当发现没有预期匹配的边后，尝试转移到其他相同的后缀子树中，听起来很熟悉，因为
KMP 也是这样的思路，只不过 KMP 是借助一个辅助数组进行失配转移，而我们给
AC 自动机中的每个点都加了一个 fail 指针。AC
自动机中的根节点用来吸收所有预期之外的字母（指fail
指针转移的终点）。
AC 自动机的每个节点都是如下结构：
1
2
3
4
5
6
7
8
9
10
11
| class ACTree {
ACTree *child[26];
ACTree *fail;
vector<int> exist;
ACTree() {
fail = nullptr;
for (int i = 0; i < 26; i++) {
child[i] = nullptr;
}
}
}
|
我们依然按照以下方式先往这棵树中添加单词，和传统字典树不同的是用
exist 数组替代了 isEnd 标记，这允许我们能从每个节点获取更多信息：
1
2
3
4
5
6
7
8
9
10
11
| void insert(const string &s) {
ACTree *cur = this;
for (auto &ch : s) {
int idx = ch - 'a';
if (cur->child[idx] == nullptr) {
cur->child[idx] = new ACTree();
}
cur = cur->child[idx];
}
cur->exist.push_back(s.length());
}
|
当 AC 自动机中的字典树构建完成后就开始进行最重要的 fail
指针构建，fail
指针指向的是所有模式串的前缀中匹配当前状态的最长后缀。我们采用层次遍历的方法去给每个节点生成
fail 指针的指向，这借助了父节点的 fail 指针信息，具体实现如下：
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
| void build(const vector<string> &s) {
int n = s.size();
for (auto &word : s) {
insert(word);
}
queue<ACTree*> q;
for (int i = 0; i < 26; i++) {
if (this->child[i] != nullptr) {
this->child[i]->fail = this;
q.push(this->child[i]);
}
}
while (!q.empty()) {
ACTree *cur = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (cur->child[i] != nullptr) {
ACTree *nxt = cur->child[i], *fafail = cur->fail;
while (fafail != nullptr && fafail->child[i] == nullptr) {
fafail = fafail->fail;
}
if (fafail == nullptr) {
nxt->fail = this;
}
else {
nxt->fail = fafail->child[i];
}
if (nxt->fail->exist.size() != 0) {
for (auto &it : nxt->fail->exist) {
nxt->exist.push_back(it);
}
}
q.push(nxt);
}
}
}
}
|
AC
自动机构建完成后就可以进行主串的匹配，其原理和自动机逻辑相同，当遇到没有匹配的边后，通过
fail 指针转移到其他子树，直到把整个字符串匹配完成，匹配过程如下：
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
|
vector<pair<int, int>> query(const string &t) {
ACTree *cur = this;
vector<pair<int, int>> ans;
for (int i = 0; i < t.length(); i++) {
int idx = t[i] - 'a';
while (cur->child[idx] == nullptr && cur->fail != nullptr) {
cur = cur->fail;
}
if (cur->child[idx] != nullptr) {
cur = cur->child[idx];
}
else {
continue;
}
if (cur->exist.size() != 0) {
for (auto &it : cur->exist) {
ans.emplace_back(make_pair(i - it + 1, i));
}
}
}
return ans;
}
|
完整代码可以通过本博客的另一篇文章《算法练习常用模板》查看。
目前字符串匹配只见到了这两种：单字符串匹配和多模式串匹配，后续遇到后缀自动机再更新一下本文。本文主要帮助我自己记忆一些思路，可能形容不是很贴切，具体可以通过
OI-WIKI
进行学习，BiliBili这个视频 轻松掌握ac自动机
讲的也很棒！