AC automata

---

Why AC automata

For a long article or string str, There are several sensitive words .
How to find out str Sensitive words in ？

The feasible solution is to traverse str, Then it matches all sensitive words at each position , If both matches fail , Go back to the next position of the first matching position , In turn . Until when str End of traversal .

But this method wastes too much time , If the total length of sensitive words is M,str Is the length of the N, It is obvious that the time complexity has come O(MN).

AC Automata is used to solve this problem efficiently .

---

AC The concept of automata

AC The basis of automata is Trie Trees （ Prefix tree ）. and Trie The difference between trees is , Each node in the tree has a pointer to the child , One more fail The pointer .

1. Every node has fail The pointer , And the root node fail The pointer points to null
2. The children of the first layer below the root node fail The pointers all point to the root node
3. In other locations fail The pointer first looks at the parent node fail Does the pointer have a path to its own? If so, let the current position of fail The pointer points to the father fail The node to which the pointer points , If you don't have this road, go through fail The pointer continues to go up , If it's empty , Then let fail The pointer points to the root node
4. fail The meaning of the pointer ： If the path that must be formed at the end of the current character is str, Which string prefix is left and str The suffix , Have the maximum matching length .fail The pointer points to the node position corresponding to that string .

How do we collect the matched sensitive words ？

A flag bit must be placed at the end of each path to indicate that the node has come to the end , As long as you get to the end, it means that the match is successful . And there will be one bool A variable of type indicates that the sensitive word has been found , Don't look for this sensitive word next time .

Every time you come to a position, follow fail The pointer goes around , See if the position has come to an end , If not, continue to match .
Or the example above ：

How to set up fail The pointer

Use width first traversal , Pop up a node cur when , look for cur Next level node of next, according to cur Of fail Whether the next position of the node pointed to is next, modify next Of fail Where the pointer points , If not, it means root.

---

Code

#include<vector>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
struct Node {
    
	// Has the answer been added to the string of table expression before 
	// If you have already joined , You don't need to add an answer next time you get a match 
	bool endUse;
	Node* fail;
	vector<Node*>nexts;
	// If end If it is not empty, it means the end of a string 
	string end;
	Node()
		:endUse(false)
		, fail(nullptr)
		, nexts(26)
		, end("")
	{
    }
};
class ACAutomation {
    
public:
	ACAutomation()
	{
    
		// Initializing a root node 
		_root = new Node;
	}
	// Same as prefix tree operation , Build prefix tree only 
	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;
	}
	// Connect fail The pointer 
	void build() 
	{
    
		// Breadth first traversal 
		queue<Node*>q;
		q.push(_root);
		Node* cur = nullptr;
		Node* cfail = nullptr;
		while (!q.empty()) 
		{
    
			// The father goes out in line to set up the children's fail The pointer 
			cur = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) 
			{
    
				// Set up cur->nexts[i] Of fail The pointer 
				if (cur->nexts[i]!=nullptr) 
				{
    
					cur->nexts[i]->fail = _root;// Point to the root node by default , If you find it later, change it again 
					// look for cur Node fail Where the pointer points 
					cfail = cur->fail;
					// seek cfail The position to which the pointer is pointing 
					while (cfail)
					{
    
						// eureka , And change the location 
						if (cfail->nexts[i]) 
						{
    
							cur->nexts[i]->fail = cfail->nexts[i];
							break;
						}
						// without , Just go up one floor fail go , Walk until you are empty , It indicates that you have reached the root node 
						cfail = cfail->fail;
					}
				}
				q.push(cur->nexts[i]);
			}
		}
	}
	// Give a long string content, Return all sensitive words to 
	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';
			// The current character is not matched on this road , Just follow fail The pointer finds another path to match 
			while (cur->nexts[index] == nullptr && cur != _root) 
			{
    
				cur = cur->fail;
			}
			// Now the path can be matched 
			// Now, the node is the root node of the prefix tree 
			cur = cur->nexts[index] != nullptr ? cur->nexts[index] : _root;
			// Go to any node and follow fail The pointer goes around 
			follow = cur;
			while (follow != _root) 
			{
    
				// It has been used to prevent repeated collection 
				if (follow->endUse) 
				{
    
					break;
				}
				// eureka 
				if (follow->end != "") 
				{
    
					ans.push_back(follow->end);
					follow->endUse = true;
				}
				follow = follow->fail;
			}
		}
		return ans;
	}
private:
	Node* _root;
};