文章目录
为什么需要AC自动机
对于一个很长的文章或者字符串str，其中有若干个敏感词。
如何找出str中的敏感词呢？
可行的办法是遍历str，然后每到一个位置就与所有敏感词匹配一遍，如果都匹配失败，再回到一开始匹配位置的下一个位置，依次往后。直到当将str遍历完。
但是这种方法太废时间了，如果敏感词的总长度是M，str的长度是N，很明显时间复杂度来到了O(MN)。
AC自动机就是用来高效解决这个问题的。
AC自动机的概念
AC自动机的基础是Trie树（前缀树）。和Trie树不同的是，树中的每个结点除了有指向孩子的指针，还有一个fail指针。
- 每个节点都有fail指针，并且根节点fail指针指向空
- 根节点下面第一层的孩子的fail指针全部指向根节点
- 其他位置的fail指针首先看父亲节点的fail指针有没有到自己的这条路如果有则让当前位置的fail指针指向父亲fail指针所指向的节点，如果没有这条路则通过fail指针继续往上走，如果走到空了，则让fail指针指向根节点
- fail指针的含义：如果必须以当前字符结尾形成的路径为str,剩下哪一个字符串的前缀和str的后缀，拥有最大的匹配长度。fail指针就指向那个字符串所对应的节点位置。
我们如何收集匹配出来的敏感词？
每条路径的结尾必须放一个标志位表示该节点已经走到头了，只要走到头就说明匹配成功。并且还要有一个bool类型的变量表示这个敏感词已经被找到了，下次就不用找这个敏感词了。
每来到一个位置跟着fail指针走一圈，看到的位置有没有走到头，没有就继续匹配。
还是上面的例子：
如何建立fail指针
使用宽度优先遍历，在弹出一个节点cur时，找cur的下一级节点next，根据cur的fail指向的节点的下一个位置是否是next，修改next的fail指针指向的位置，如果不是就指root。
代码
#include<vector>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
struct Node {
//表式这个字符串之前有没有加入过答案
//如果已经加入了，下次匹配到就不需要加入答案了
bool endUse;
Node* fail;
vector<Node*>nexts;
//如果end不为空则表示某个字符串的结尾
string end;
Node()
:endUse(false)
, fail(nullptr)
, nexts(26)
, end("")
{}
};
class ACAutomation {
public:
ACAutomation()
{
//初始化一个根节点
_root = new Node;
}
//和前缀树操作一样，只建前缀树
void insert(const string& str)
{
Node* cur = _root;
int index = 0;
for (int i = 0; i < str.size(); i++) {
index = str[i] - 'a';
if (cur->nexts[index] == nullptr)
{
cur->nexts[index] = new Node;
}
cur = cur->nexts[index];
}
cur->end = str;
}
//连接fail指针
void build()
{
//宽度优先遍历
queue<Node*>q;
q.push(_root);
Node* cur = nullptr;
Node* cfail = nullptr;
while (!q.empty())
{
//父亲出队列设置孩子的fail指针
cur = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
//设置cur->nexts[i]的fail指针
if (cur->nexts[i]!=nullptr)
{
cur->nexts[i]->fail = _root;//先默认指向根节点，后面如果找到了就重新改
//找cur节点的fail指针指向的位置
cfail = cur->fail;
//寻找cfail指针的要指向的位置
while (cfail)
{
//找到了，并修改位置
if (cfail->nexts[i])
{
cur->nexts[i]->fail = cfail->nexts[i];
break;
}
//如果没有，就往上一层fail走，一直走到空，说明走到了根节点
cfail = cfail->fail;
}
}
q.push(cur->nexts[i]);
}
}
}
//给一个长字符串content，将其中的敏感词都返回
vector<string>containWords(const string& content)
{
Node* cur = _root;
Node* follow = nullptr;
vector<string>ans;
int index = 0;
for (int i = 0; i < content.size(); i++)
{
index = content[i] - 'a';
//当前字符在这条路上没有配出来，就随着fail指针找另一条路径进行匹配
while (cur->nexts[index] == nullptr && cur != _root)
{
cur = cur->fail;
}
//现在来到的路径是可以继续匹配的
//现在来到的节点就是前缀树的根节点
cur = cur->nexts[index] != nullptr ? cur->nexts[index] : _root;
//来到任何一个节点顺着fail指针走一圈
follow = cur;
while (follow != _root)
{
//已经使用过了防止重复收集
if (follow->endUse)
{
break;
}
//找到了
if (follow->end != "")
{
ans.push_back(follow->end);
follow->endUse = true;
}
follow = follow->fail;
}
}
return ans;
}
private:
Node* _root;
};
