AC自動(dòng)機(jī)，我知道很多人看到這個(gè)會(huì)十分好奇，不過這個(gè)自動(dòng)機(jī)它又叫做 Automaton。我相信大家在初學(xué)自動(dòng)機(jī)相關(guān)內(nèi)容時(shí)，許多人難以建立對(duì)自動(dòng)機(jī)的初步印象，尤其是在自學(xué)的時(shí)侯。讓我們切入正題，通過這段時(shí)間對(duì)自動(dòng)機(jī)的研究，然后制作若干的gif，已經(jīng)可以呈現(xiàn)出一個(gè)相對(duì)直觀的自動(dòng)機(jī)形態(tài)，我們先對(duì)基礎(chǔ)的知識(shí)有個(gè)了解。

定義：AC自動(dòng)機(jī)是以Trie的結(jié)構(gòu)為基礎(chǔ)，結(jié)合KMP的思想建立的。

什么是AC自動(dòng)機(jī)？

1. AC自動(dòng)機(jī)是一種有限狀態(tài)自動(dòng)機(jī)（說了等于沒說），它常被用于多模式串的字符串匹配。

2. 在學(xué)完AC自動(dòng)機(jī)后，總結(jié)為： AC自動(dòng)機(jī)是以Trie的結(jié)構(gòu)為基礎(chǔ)，結(jié)合KMP的思想建立的。 

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

簡單來說，建立一個(gè) AC 自動(dòng)機(jī)有兩個(gè)步驟：

（1）基礎(chǔ)的Trie結(jié)構(gòu)：將所有的模式串構(gòu)成一棵Trie樹。

（2）KMP的思想：對(duì)Trie樹上所有的結(jié)點(diǎn)構(gòu)造失配指針，然后就可以利用它進(jìn)行多模式匹配了。

關(guān)于Trie樹構(gòu)造

和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; //沒有這個(gè)字母的邊的話，新建一條
		u = ch[u][c]; //接著往下跳
	}
	bo[u]++; //將這個(gè)點(diǎn)標(biāo)記為一個(gè)單詞的結(jié)尾
	return;
}

這并不是關(guān)于AC自動(dòng)機(jī)的詳細(xì)內(nèi)容，但是可以幫助大家先理性的認(rèn)識(shí)，后期多練習(xí)。