AC自动机

---

为什么需要AC自动机

对于一个很长的文章或者字符串str，其中有若干个敏感词。
如何找出str中的敏感词呢？

可行的办法是遍历str，然后每到一个位置就与所有敏感词匹配一遍，如果都匹配失败，再回到一开始匹配位置的下一个位置，依次往后。直到当将str遍历完。

但是这种方法太废时间了，如果敏感词的总长度是M，str的长度是N，很明显时间复杂度来到了O(MN)。

AC自动机就是用来高效解决这个问题的。

---

AC自动机的概念

AC自动机的基础是Trie树（前缀树）。和Trie树不同的是，树中的每个结点除了有指向孩子的指针，还有一个fail指针。

1. 每个节点都有fail指针，并且根节点fail指针指向空
2. 根节点下面第一层的孩子的fail指针全部指向根节点
3. 其他位置的fail指针首先看父亲节点的fail指针有没有到自己的这条路如果有则让当前位置的fail指针指向父亲fail指针所指向的节点，如果没有这条路则通过fail指针继续往上走，如果走到空了，则让fail指针指向根节点
4. 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;
};