AC自動(dòng)機(jī)（Aho-Corasick\ automaton）刻炒，可以解決多模板串匹配的問(wèn)題茂嗓』闭樱可以理解為可以一次性匹配很多串的KMP伍宦。在KMP中凉敲，有一個(gè)失配函數(shù)next化撕，在AC自動(dòng)機(jī)中儡毕，也有一個(gè)類(lèi)似的失配函數(shù)fail簇捍。類(lèi)似于KMP的轉(zhuǎn)移乙帮，每當(dāng)AC自動(dòng)機(jī)失配時(shí)杜漠，也會(huì)相應(yīng)地轉(zhuǎn)到當(dāng)前節(jié)點(diǎn)的fail。
Trie
為了一次性高效地匹配字符串察净，我們需要用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)所有的模板串驾茴。這個(gè)數(shù)據(jù)結(jié)構(gòu)就叫Trie∪蹋可以把Trie叫做字典樹(shù)沟涨，所以Trie是一棵樹(shù)。比如下面這個(gè)
這個(gè)就是一棵包含ab,abc,bd,dda四個(gè)串的Trie异吻。通過(guò)觀察裹赴，我們可以發(fā)現(xiàn)
根節(jié)點(diǎn)不包含字符
從根節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)簡(jiǎn)單路徑上的字母即是這個(gè)節(jié)點(diǎn)代表的串
串的終點(diǎn)有標(biāo)記
每次匹配，我們從Trie的根節(jié)點(diǎn)出發(fā)诀浪，嘗試用文本串去匹配Trie樹(shù)棋返，由于Trie樹(shù)將一些字符串壓縮到了一起，因此時(shí)間復(fù)雜度會(huì)大大降低雷猪。但注意睛竣，Trie樹(shù)是一種用空間換時(shí)間的做法
部分代碼：
void init() {memset(trie[0],0,sizeof(trie[0])),ncnt=0;}
void insert(char s[],int len,int n) {//插入新串
int now=0,c;
for (int i=1;i<=len;i++) {//查找路徑（沒(méi)有則添加）
c=idx(s[i]);
if (trie[now][c]==0)
now=trie[now][c]=++ncnt,memset(trie[now],0,sizeof(trie[now]));
else now=trie[now][c];
}
val[now]=n;//標(biāo)記終點(diǎn)
}
Trie樹(shù)的空間復(fù)雜度是O(nmt)，n是串的總數(shù)求摇，m是最長(zhǎng)串的長(zhǎng)度射沟，t是節(jié)點(diǎn)字母的種類(lèi)
AC自動(dòng)機(jī)實(shí)現(xiàn)
我們引入一個(gè)新的數(shù)組last，代表與當(dāng)前節(jié)點(diǎn)有最長(zhǎng)后綴的串在Trie上的編號(hào)与境。很明顯验夯，假如當(dāng)前串匹配成功了，那么它的last也一定可以匹配成功（是它的后綴八さ蟆）
last的一個(gè)重要性質(zhì)： 設(shè)p的失敗指針指向節(jié)點(diǎn)k挥转，則它應(yīng)該滿(mǎn)足這樣的性質(zhì)：從root到k的字符串完全匹配于從p往上相同長(zhǎng)度的后綴
注意last與fail的區(qū)別：last是指當(dāng)前節(jié)點(diǎn)的某個(gè)出現(xiàn)在模板串之中的后綴，而fail則不要求出現(xiàn)在模板串中
如果當(dāng)前串匹配失敗，那么就一直跳fail绑谣。我們這樣考慮：
假設(shè)s[1,i]已經(jīng)匹配成功了党窜，第i個(gè)字符對(duì)應(yīng)Trie上的u號(hào)節(jié)點(diǎn)，但是s[i+1]匹配失敗了借宵，很明顯幌衣，我們可以從u節(jié)點(diǎn)跳到它的
fail。因?yàn)?span id="7g2v0mz" class="math-inline">s[1,i]已經(jīng)匹配成功了暇务，那么s[1,i]的某個(gè)后綴（對(duì)應(yīng)fail）也一定可以匹配成功
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];
舉個(gè)例子
我們考慮這樣一個(gè)自動(dòng)機(jī)
這是一棵倒著的Trie加上一些虛線(xiàn)箭頭一個(gè)AC自動(dòng)機(jī)的狀態(tài)圖泼掠，綠色的點(diǎn)代表有標(biāo)記。至于點(diǎn)上的數(shù)垦细，可以暫時(shí)不管择镇。
實(shí)線(xiàn)代表Trie上的邊，虛線(xiàn)代表fail指向的節(jié)點(diǎn)
觀察91這個(gè)點(diǎn)括改，它表示的串是SHE腻豌，它的fail指針指向76號(hào)點(diǎn)，這個(gè)點(diǎn)表示的串是HE嘱能，可以發(fā)現(xiàn)吝梅，它是SHE的一個(gè)后綴。
我們考慮在這樣一棵Trie上匹配串SHERS
1.當(dāng)前位于根節(jié)點(diǎn)惹骂，對(duì)應(yīng)字符S苏携，因此走85號(hào)點(diǎn)，匹配成功
2.當(dāng)前位于85號(hào)點(diǎn)对粪，對(duì)應(yīng)字符H右冻，因此走90號(hào)點(diǎn)，匹配成功
3.當(dāng)前位于90號(hào)點(diǎn)著拭，對(duì)應(yīng)字符E纱扭，因此走91號(hào)點(diǎn)，匹配成功
4.91號(hào)點(diǎn)被標(biāo)記過(guò)儡遮，匹配數(shù)+1
5.當(dāng)前位于91號(hào)點(diǎn)乳蛾，對(duì)應(yīng)字符R，這個(gè)點(diǎn)沒(méi)有字符為R的點(diǎn)鄙币，匹配失敗肃叶，跳到91號(hào)點(diǎn)的fail指針76號(hào)點(diǎn)
6.當(dāng)前位于76號(hào)點(diǎn)，對(duì)應(yīng)字符R十嘿，因此走160號(hào)點(diǎn)因惭，匹配成功
7.當(dāng)前位于160號(hào)點(diǎn)，對(duì)應(yīng)字符S详幽，因此走86號(hào)點(diǎn)，匹配成功
8.至此，串SHERS已匹配完成
代碼實(shí)現(xiàn)如下
void query(char s[],int len) {
int now=0;
for (int i=1;i<=len;i++) {
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];//匹配失敗唇聘，則一直跳fail指針
now=trie[now][c];
if (val[now]) cnt[val[now]]++;//匹配成功版姑，且當(dāng)前節(jié)點(diǎn)是某個(gè)模板串的末尾
int las=last[now];
while (val[las]) val[las]=0,cnt[val[las]]++,las=last[las];//當(dāng)前節(jié)點(diǎn)匹配成功，它的last也一定匹配成功
}
}
接下來(lái)是AC自動(dòng)機(jī)的關(guān)鍵部分迟郎，即預(yù)處理fail指針與last指針
由于一個(gè)節(jié)點(diǎn)的fail的深度一定小于這個(gè)點(diǎn)的深度剥险，所以我們考慮用bfs實(shí)現(xiàn)
考慮從一個(gè)已經(jīng)求出fail與last的節(jié)點(diǎn)now轉(zhuǎn)移到他的后繼節(jié)點(diǎn)son
如果now的fail指針有與son相同的后繼節(jié)點(diǎn)，那么直接轉(zhuǎn)移到那個(gè)后繼節(jié)點(diǎn)宪肖。否則一直跳fail表制，直到根節(jié)點(diǎn)。
for (int i=0;i<128;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i];
}
如果now節(jié)點(diǎn)所指向的fail的這個(gè)兒子已經(jīng)被標(biāo)記過(guò)控乾，即是某個(gè)模板串的結(jié)尾么介，就直接將其賦到son，否則一直跳last
last[son]=val[fail[son]]?fail[son]:last[fail[son]];
總bfs實(shí)現(xiàn)如下
void bfs() {
queue<int> q;
while (!q.empty()) q.pop();
fail[0]=last[0]=0;
for (int i=0;i<26;i++) {
int now=trie[0][i];
if (now) fail[now]=last[now]=0,q.push(now);
}
while (!q.empty()) {
int now=q.front();q.pop();
for (int i=0;i<26;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i],last[son]=val[fail[son]]?fail[son]:last[fail[son]];
q.push(son);
}
}
}
最后是AC自動(dòng)機(jī)模板代碼
int ncnt=0,trie[100010][26],val[100010];
int idx(char c) {return c-'a';}
void init() {memset(trie[0],0,sizeof(trie[0])),ncnt=0;}
void insert(char s[],int len,int n) {
int now=0,c;
for (int i=1;i<=len;i++) {
c=idx(s[i]);
if (trie[now][c]==0)
now=trie[now][c]=++ncnt,memset(trie[now],0,sizeof(trie[now]));
else now=trie[now][c];
}
val[now]=n;//val里存的是串的編號(hào)
}
int fail[100010],last[100010];
void bfs() {
queue<int> q;
while (!q.empty()) q.pop();
fail[0]=last[0]=0;
for (int i=0;i<26;i++) {
int now=trie[0][i];
if (now) fail[now]=last[now]=0,q.push(now);
}
while (!q.empty()) {
int now=q.front();q.pop();
for (int i=0;i<26;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i],last[son]=val[fail[son]]?fail[son]:last[fail[son]];
q.push(son);
}
}
}
int cnt[510];
void query(char s[],int len) {
int now=0;
for (int i=1;i<=len;i++) {
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];
now=trie[now][c];
if (val[now]) cnt[val[now]]++;
int las=last[now];
while (val[las]) val[las]=0,cnt[val[las]]++,las=last[las];
}
}
