什么是AC自动机？

AC自动机，我知道很多人看到这个会十分好奇，不过这个自动机它又叫做 Automaton。我相信大家在初学自动机相关内容时，许多人难以建立对自动机的初步印象，尤其是在自学的时侯。让我们切入正题，通过这段时间对自动机的研究，然后制作若干的gif，已经可以呈现出一个相对直观的自动机形态，我们先对基础的知识有个了解。

定义：AC自动机是以Trie的结构为基础，结合KMP的思想建立的。

什么是AC自动机？

1. AC自动机是一种有限状态自动机（说了等于没说），它常被用于多模式串的字符串匹配。

2. 在学完AC自动机后，总结为： AC自动机是以Trie的结构为基础，结合KMP的思想建立的。 

注意：（AC = KMP + Trie) 但不完全是。

简单来说，建立一个 AC 自动机有两个步骤：

（1）基础的Trie结构：将所有的模式串构成一棵Trie树。

（2）KMP的思想：对Trie树上所有的结点构造失配指针，然后就可以利用它进行多模式匹配了。

关于Trie树构造

和trie树的插入操作一样，将模式串存入

void insert(char *s){
	int u=1,len=strlen(s); //从1开始跳
	for(register int i(0) ; i<len ; i=-~i){
		int c=s[i]-'a';
		if(!ch[u][c]) ch[u][c] = ++tot; //没有这个字母的边的话，新建一条
		u = ch[u][c]; //接着往下跳
	}
	bo[u]++; //将这个点标记为一个单词的结尾
	return;
}

这并不是关于AC自动机的详细内容，但是可以帮助大家先理性的认识，后期多练习。