一：概念

首先简要介绍一下AC自己主动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之中的一个。一个常见的样例就是给出n个单词，再给出一段文章（长度是m），让你找出有多少个单词在文章里出现过。

要搞懂AC自己主动机。先得有字典树Trie的基础知识（也有人说需要KMP的知识，我认为暂且不要理会这个。

可是在看这篇文章之前，Trie字典树，你是必需要先搞懂，假设你还不理解Trie，请參考）。

与其它字符匹配不同，KMP算法是单模式串的字符匹配算法，AC自己主动机是多模式串的字符匹配算法。匹配时间复杂度是O(N)。线性复杂度！

二：算法过程（三步走）

举个样例，假如如今给出5个模式串：say she shr he her 

主串是：yasherhs

如今问你，这5个模式串有几个出如今主串里的？

OK，如今就拿这个样例来完毕这个算法的过程。

第一步：构建Trie树，这非常easy的了。

构建好后。出现下图：

第二步：构建失败指针

构建失败指针是AC自己主动机的核心所在，玩转了它也就玩转了AC自己主动机，失败指针就是。当我的主串在trie树中进行匹配的时候，假设当前节点不能再继续进行匹配。那么我们就会走到当前节点的fail节点继续进行匹配。

构造失败指针的过程概括起来就一句话：对于root的儿子节点。fail指针直接指向root，其它的全部节点（用到了BFS和队列），设这个节点上的字母为C。沿着它父亲的失败指针走。直到走到一个节点，它的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母为C的节点。

假设一直走到了root都没找到，那就把失败指针指向root。

构建好后，例如以下图：

针对图中红线的”h。e“这两个节点。我们想起了什么呢？对”her“中的”e“来说，e到root距离的n个字符恰好与”she“中的e向上的n个字符相等。

第三步：模式匹配

匹配过程分两种情况：

(1)  当前字符匹配成功，表示从当前节点沿着树边有一条路径能够到达目标字符，此时仅仅需沿该路径走向下一个节点继续匹配就可以，目标字符串指针移向下个字符继续匹配；

(2)  当前字符不匹配，则去当前节点失败指针所指向的字符继续匹配，匹配过程随着指针指向root结束。反复这2个过程中的随意一个。直到模式串走到结尾为止。

注意：主串全部字符在匹配完后都必需要走fail节点来结束自己的旅途,相当于一个回旋，这样做的目的防止包括节点被忽略掉。

见下图，比方：我匹配到了"she"，必定会匹配到该字符串的后缀”he"，要想在程序中匹配到，则必须节点要走失败指针来结束自己的旅途。

三：完整代码

#include
     
      #include
      
       #define MAX 26//如果仅仅出现26个小写英文字母#define ROW 4#define COLUMN 10using namespace std;char pattern[ROW][COLUMN] = { "nihao","hao","hs","hsr" };char *s = "sdmfhsgnshejfgnihaofhsrnihao";struct Node{	int index;//存储模式串的下标	char x;	Node *parent;	Node *next[MAX];	Node *fail;	Node()	{		index = -1;//pattern数组下标从0開始，-1代表该节点不是单词结尾		fail = nullptr; 		parent = nullptr;		for (int i = 0; i < MAX; i++)			next[i] = nullptr;	}};class ACTree{public:	Node *root;	ACTree() { root = new Node; root->fail = root; }	void Add(const char *ch, int index);              //第一步	void NodeToQueue(Node *node, queue
       
         &q);    //	void BuildFailPointer();                          //第二步	void ACSearch(const char *s);                     //第三步};int main() {	ACTree tree;	for (int i = 0; i < ROW; i++)		tree.Add(pattern[i], i);	tree.BuildFailPointer();	cout << "待匹配字符串为（依次5个一组的输出）：\n";	for (int i = 1; i <= strlen(s); i++)	{		cout << s[i];		if (i % 5 == 0)			cout << "  ";	}	cout << endl << endl;	cout << "匹配结果例如以下：\n";	cout << "位置\t" << "编号\t" << "模式\n";	tree.ACSearch(s);	return 0;}void ACTree::Add(const char *ch,int index){	int len = strlen(ch);	if (len == 0) return;	Node *p = root;	for (int i = 0; i < len; i++)	{		int k = ch[i] - 'a';		if (p->next[k] == nullptr)		{			p->next[k] = new Node;			p->next[k]->parent = p;			p->next[k]->x = ch[i];		}				p = p->next[k];	}	p->index = index;//注意，在此保证输入的模式串不反复,否则index会被覆盖}void ACTree::NodeToQueue(Node *node, queue
        
          &q){	if (node != nullptr)	{		for (int i = 0; i < MAX; i++)		{			if (node->next[i])				q.push(node->next[i]);//不知道这是干嘛的？？想想BFS层次遍历的那些事		}	}}void ACTree::BuildFailPointer(){	queue
         
           q;	for (int i = 0; i < MAX; i++)	{		if (root->next[i])		{			NodeToQueue(root->next[i], q);//注意。切不可写成q.push(root->next[i]);			root->next[i]->fail = root;		}	}	Node *parent, *p;	char ch;	while (!q.empty())	{		p = q.front();		ch = p->x;		parent = p->parent;		q.pop();		NodeToQueue(p, q);		while (1)		{			if (parent->fail->next[ch - 'a'] != nullptr)			{				p->fail = parent->fail->next[ch - 'a'];				break;			}			else			{				if (parent->fail == root)				{					p->fail = root;					break;				}				else					parent = parent->fail->parent;			}		}	}}void ACTree::ACSearch(const char *s){	int len = strlen(s);	if (len == 0) return;	Node *p = root;	int i = 0;	while (i < len)	{		int k = s[i] - 'a';		if (p->next[k] != nullptr)		{			p = p->next[k];			if (p->index != -1)				cout << i - strlen(pattern[p->index]) + 1 << "\t" << p->index << "\t" << pattern[p->index] << endl;			i++;		}		else		{			if (p == root)				i++;			else			{				p = p->fail;				if (p->index != -1)					cout << i - strlen(pattern[p->index]) + 1 << "\t" << p->index << "\t" << pattern[p->index] << endl;			}		}	}	while (p != root)	{		p = p->fail;		if(p->index!=-1)			cout << i - strlen(pattern[p->index]) + 1 << "\t" << p->index << "\t" << pattern[p->index] << endl;	}}
         
        
       
      
     

四：数据測试

返回文件夹---->