「字符串」详解AC自动机并实现对应的功能 / 手撕数据结构（C++）

目录

前置知识

概述

核心概念：fail指针

作用

构建

图示

Code

成员变量

创建销毁

添加词库

文本扫描

复杂度 

Code

---

前置知识

在此前，你应该首先了解trie树（字典树）的概念：

「字符串」详解Trie（字典树|前缀树）并实现对应的功能 / 手撕数据结构（C++）

我们建议你先阅读这篇文章，以了解我们实现字典树所用的一些结构，比如trie_node，以及词尾节点存储了整个字符串这些概念。

---

概述

AC自动机是能以线性时间复杂度对整个文本进行黑名单词汇统计的数据结构。

我们先将黑名单语句词库逐条插入这棵字典树。当我们扫描文本时，就能以一次遍历实现对文本中所有出现的黑名单库中的语句进行统计。

你应该这样认识AC自动机：它首先是一颗字典树，其次是它还有一个成员：fail指针数组。

就如同他的名字一样，这个自动机结构会根据输入的内容自动地调整内部的行为，这就是它能以单次扫描就匹配全部文本的奥妙之处。

---

核心概念：fail指针

作为一颗独特的字典树，AC自动机还有fail指针数组。

作用

它的定义是：trie_node* fail[i]；

fail指针，顾名思议，它会在匹配失败时指向另一个可行的节点。

这个数组是干什么的？你可以认为如果我们的匹配失败，那么fail指针就会启动，并跳转到一个具有和当前节点相同字符的节点上，例如fail[5]存储了与5号节点具有相同字符的节点地址。

这样讲似乎很让人不能理解，我们来看这张图：

预先插入了以上敏感词字符串。如果我们要匹配的是“sher”，如果进行朴素匹配那么我们只能得到“she”，但我们知道有三个字符串“she”“he”“her”都在其中，我们怎么才能只扫描一次就得到这些字符串呢？fail指针做了这件事。

当我们匹配到字符'r'时，发现无法继续，此时fail指针发力了，由于位于5号节点，而fail[5]->8号节点的地址，所以我们可以跳转到8号节点继续匹配。

这样一来“she”“he”“her”就全部匹配上了。

下面我们来说说fail指针是怎么构建的。

构建

有三条原则：

1.root节点的fail指针指向自己，此后按层遍历，进行各个层次的fail指针的构建。

2.如果某节点A的fail指针指向另一非root节点B，那么A的字符与B的字符是相同的。如fail[5]->8号节点。

3.如果当前节点child1的父节点father1的fail指针指向另一节点father2，而father2名下恰好有与child1同字符的child2，那么fail[child1]->child2，如果没有同字符的child2，那么fail[child1]->root。

我们重点解释第三条：这是为了保证我们的匹配是有效的：

如果fail[father1]->father2，那么father1与father2是相同字符节点，那么可以保证从child1通过fail指针跳转到child2时，他们前面匹配过得一部分字符串（即father1和father2）是相同的，这样一来，可以保证在我们进行文本匹配时，不会出现3号节点跳转到6号节点（看上图）的现象。

*注意*：也有child1跳转到child2时不存在前面匹配过的一部分字符串，即child1的字符可能是某个敏感词的首字符，这时候跳转到root进行匹配（即第三条规则的最后一句话）。

图示

我们希望你结合以上三条规则在图上画出全部fail指针，在此我们给出答案：

Code

node->idx代表节点编号，它同时担任了fail指针数组下标的功能。

std::vector <trie_node*> fail;
void bulid_fail() {fail.resize(val_size,root);std::queue<trie_node*>que;que.push(root);while (!que.empty()) {int len = que.size();while (len--) {trie_node* node = que.front(); que.pop();for (int i = 0; i < branches; i++) {trie_node*& father= node;trie_node*& child = node->next[i];if (child != nullptr) {que.push(child);if (fail[father->idx]->next[i] != nullptr&&fail[father->idx]->next[i]!=child)fail[child->idx] = fail[father->idx]->next[i];}}}}//int i = 0;//for (const trie_node* node : fail)std::cout << i++ << "->" << node->idx << std::endl;
}

接下来，我们封装AC_automaton类，实现AC自动机的基本功能。（Code和测试案例附后）

---

成员变量

ac自动机以私有方式继承trie树，并封装std::vector <trie_node*> fail指针。

class AC_automaton:private trie{
private:std::vector <trie_node*> fail;...
public:...}
};

---

创建销毁

提供三种构造，一种析构函数，。

这些内容均于「字符串」详解Trie（字典树|前缀树）并实现对应的功能 / 手撕数据结构（C++）中提及。

我们删除了复制构造和复制赋值等于号，以防止两份AC自动机的fail指针指向同一组地址。

AC_automaton(int branch = 128) :trie(branch), fail(1, root) {};
AC_automaton(const trie& data) :trie(data), fail(1,root) {bulid_fail();
};
AC_automaton(const AC_automaton& another) = delete;
AC_automaton(const std::initializer_list<std::string> ini_list) :trie(ini_list), fail(1, root) {bulid_fail();
}
~AC_automaton() {};
AC_automaton& operator=(const AC_automaton& another) = delete;

---

添加词库

提供insert_blackedlist与它的重载，支持单条语句和多语句插入。

随后调用build_fail重建fail指针。

void insert_blacklist(const std::string str) {trie::insert(str);bulid_fail();
}
void insert_blacklist(const std::vector<std::string> strs) {trie::insert(strs);bulid_fail();
}

---

文本扫描

文本扫描是AC自动机的另一个核心部分，它是fail指针的具体应用。

初始化指针p指向根节点。text为待扫描文本。

对于这个流程，我们总结为以下几点：

1.当p指向根节点并且黑名单字符串库不存在当前text[i]开头的字符，那么跳过当前字符。

2.当p指针指向的节点储存了str黑名单字符串，将其加入统计结果。

3.当p指针无法继续向下匹配，启动fail指针，前往fail[p->idx]（p->idx表示当前节点的序号，fail[p->idx]存储当前节点的跳转位置）

*注意*：因为跳转后的节点字符与跳转前的节点字符相同，此时请不要向后移动text文本字符，即不要进行i++操作，这会导致匹配错位。

4.脱离循环后将p位置可能存在的字符串加入统计结果，以及p位置的fail指针指向的节点也可能有字符串，他们都需要加入统计结果。这是由于p抵达最后一个字符时循环已经结束，并且fail指针有着p的相同前缀以及相同字符，他们都有可能成为统计结果。

std::vector<std::string> query(std::string text) {std::vector<std::string> ans;trie_node* p = root;const int len = text.size();for (int i = 0; i < len;) {if (p == root && p->next[text[i]] == nullptr)i++;if (p->str.empty()==false)ans.push_back(p->str);if (p->next[text[i]] != nullptr)p = p->next[text[i++]];else p = fail[p->idx];}if (p->str.empty() == false)ans.push_back(p->str);if(fail[p->idx]->str.empty()==false); ans.push_back(fail[p->idx]->str);return ans;
}

---

复杂度 

时间复杂度：插入：O(n*m) 扫描：O(m)

空间复杂度：插入：O(n*m) 扫描：O(1)

n：插入字符串数目

m：插入/待扫描字符串长度

---

Code

#include <queue>
#include "trie.h"
#ifndef AC_AUTOMATON
#define AC_AUTOMATON
class AC_automaton:private trie{
private:std::vector <trie_node*> fail;void bulid_fail() {fail.resize(val_size,root);std::queue<trie_node*>que;que.push(root);while (!que.empty()) {int len = que.size();while (len--) {trie_node* node = que.front(); que.pop();for (int i = 0; i < branches; i++) {trie_node*& father= node;trie_node*& child = node->next[i];if (child != nullptr) {que.push(child);if (fail[father->idx]->next[i] != nullptr&&fail[father->idx]->next[i]!=child)fail[child->idx] = fail[father->idx]->next[i];}}}}//int i = 0;//for (const trie_node* node : fail)std::cout << i++ << "->" << node->idx << std::endl;}
public:AC_automaton(int branch = 128) :trie(branch), fail(1, root) {};AC_automaton(const trie& data) :trie(data), fail(1,root) {bulid_fail();};AC_automaton(const AC_automaton& another) = delete;AC_automaton(const std::initializer_list<std::string> ini_list) :trie(ini_list), fail(1, root) {bulid_fail();}~AC_automaton() {};AC_automaton& operator=(const AC_automaton& another) = delete;void insert_blacklist(const std::string str) {trie::insert(str);bulid_fail();}void insert_blacklist(const std::vector<std::string> strs) {trie::insert(strs);bulid_fail();}std::vector<std::string> query(std::string text) {std::vector<std::string> ans;trie_node* p = root;const int len = text.size();for (int i = 0; i < len;) {if (p == root && p->next[text[i]] == nullptr)i++;if (p->str.empty()==false)ans.push_back(p->str);if (p->next[text[i]] != nullptr)p = p->next[text[i++]];else p = fail[p->idx];}if (p->str.empty() == false)ans.push_back(p->str);if(fail[p->idx]->str.empty()==false); ans.push_back(fail[p->idx]->str);return ans;}
};
#endif

测试 

#include <iostream>
#include "AC_automaton.h"
using namespace std;
int AC_automaton_test() {AC_automaton ACA = { "say","she","shy","he","her","hee","ee"};vector<string>&& ans = ACA.query("sherhee");cout << "-----------------test-----------------" << endl;for (const string& str : ans)cout << str << endl;;return 0;
}