AC自動(dòng)機(jī)就是在Trie樹上加入一些失敗指針（fail，類似KMP中的next），使得它在某個(gè)結(jié)點(diǎn)失配的時(shí)候能夠轉(zhuǎn)移到該結(jié)點(diǎn)失敗指針指向的結(jié)點(diǎn)繼續(xù)匹配，從而實(shí)現(xiàn)多串匹配（單主串多子串）。
【1】Trie樹的結(jié)構(gòu)：
首先是結(jié)點(diǎn)類型：
struct node {
int mul, ch[SZ], fail;
} T[MAXN];
其中SZ是字符集的大小，比如小寫字母集SZ=26，數(shù)字集SZ=10等。
另外這個(gè)mul表示的是該結(jié)點(diǎn)的重復(fù)次數(shù)（和平衡樹中的比較像），就是這個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的字符串（從根到該結(jié)點(diǎn)路徑上的所有邊上的字符組成的字符串）出現(xiàn)了幾次。
（不過這種表示法MS不是很好……如果有卡空間的，比如結(jié)點(diǎn)總數(shù)和SZ之積達(dá)到了100M以上，而真正的邊又很少的時(shí)候……就囧掉了……而如果用指針的話在Linux下面又會(huì)CE掉……各位神犇來說一下怎么解決啊囧……）
然后，Trie樹的0號(hào)結(jié)點(diǎn)（T[0]）是空結(jié)點(diǎn)（用來代替指針中的NULL），因此真正結(jié)點(diǎn)下標(biāo)從1開始。1號(hào)結(jié)點(diǎn)（T[1]）一般都作為根結(jié)點(diǎn)，所以下面直接寫#define root 1。
還有（這句話是除草用的……）Trie樹的字符全部都在邊上而不在點(diǎn)上，因此T[x].ch[c]其實(shí)指的是“結(jié)點(diǎn)x引出的字符為c的邊所指向的結(jié)點(diǎn)”，簡(jiǎn)稱結(jié)點(diǎn)x的c子結(jié)點(diǎn)。
【2】自動(dòng)機(jī)的建立：
首先要建立Trie樹（也就是在空的Trie樹上插入所有要匹配的子串）。這個(gè)隨便搞一下就傻掉了，因此直接上代碼：
void ins()
{
int len = s0.length(), x = root, c;
re(i, len) {
c = s0[i] - 97;
if (!T[x].ch[c]) {T[x].ch[c] = ++N; T[N].mul = 0; re(j, SZ) T[N].ch[j] = 0;}
x = T[x].ch[c];
}
T[x].mul++;
}
這里string s0是待插入的字符串，定義成全局變量，因?yàn)樵趨?shù)中出現(xiàn)string有可能爆掉。
然后就是建立自動(dòng)機(jī)了。
這一過程其實(shí)是用BFS遍歷來實(shí)現(xiàn)的。首先，T[root].fail=0（root也是整棵樹中唯一的fail為0的結(jié)點(diǎn)）并將root入隊(duì)。下面按照BFS的順序依次取出隊(duì)所有的點(diǎn)，對(duì)于結(jié)點(diǎn)i，若它存在k子結(jié)點(diǎn)j（也就是j=T[i].ch[k]，且j≠0），則結(jié)點(diǎn)j入隊(duì)，并計(jì)算j的失敗指針fail，方法：從T[i].fail（不是i）開始不斷上溯，直到找到一個(gè)存在k子結(jié)點(diǎn)的結(jié)點(diǎn)或者到root都木有找到（結(jié)點(diǎn)下標(biāo)為0，即NULL）。若找到了一個(gè)存在k子結(jié)點(diǎn)的結(jié)點(diǎn)x，則將T[j].fail置為T[x].ch[k]，否則（直到root都木有找到），T[j].fail=root。
到這里失敗指針的用處就顯現(xiàn)了：如果匹配到結(jié)點(diǎn)x的時(shí)候失配（即接下來的一個(gè)字符是c而T[x].ch[c]=0），可以立刻轉(zhuǎn)到T[x].fail進(jìn)行匹配，因?yàn)門[x].fail有以下三個(gè)特征：
<1>其深度嚴(yán)格小于x的深度；
<2>其代表的字符串一定是x代表的字符串的后綴；
<3>該結(jié)點(diǎn)一定是滿足條件<1><2>的所有結(jié)點(diǎn)中深度最小的結(jié)點(diǎn)；
代碼：
void mkf()
{
Q[0] = root; T[root].fail = 0;
int i, j, x;
for (int front=0, rear=0; front<=rear; front++) {
i = Q[front];
re(k, SZ) if (j = T[i].ch[k]) {
x = T[i].fail;
while (x && !T[x].ch[k]) x = T[x].fail;
if (x) T[j].fail = T[x].ch[k]; else T[j].fail = root;
Q[++rear] = j;
}
}
}
【3】匹配過程：
在有了失敗指針時(shí)，其匹配過程就和KMP差不多了。
設(shè)主串為A（代碼中同），依次掃描A[0..A.length()-1]進(jìn)行匹配。設(shè)目前匹配到了第i位，A[i]=c，當(dāng)前結(jié)點(diǎn)為x。匹配過程中將進(jìn)行以下操作：
<1>成功匹配（T[x]有c子結(jié)點(diǎn)），則進(jìn)入T[x]的c子結(jié)點(diǎn)；
<2>失配（T[x]無c子結(jié)點(diǎn)），則從T[x].fail開始，沿著失敗指針上溯，直到找到一個(gè)有c子結(jié)點(diǎn)的結(jié)點(diǎn)為止。如果到了root都木有找到這樣的結(jié)點(diǎn)，則停止在root處；
<3>設(shè)立結(jié)點(diǎn)y，從當(dāng)前的結(jié)點(diǎn)x開始不斷上溯到root（注意root也要算，因?yàn)樽哟锌赡苡锌沾瑢⒅虚g所有結(jié)點(diǎn)的mul值累加進(jìn)最終結(jié)果（表示這些字符串在主串中出現(xiàn)了，統(tǒng)計(jì)次數(shù)），如果題目中要求統(tǒng)計(jì)不重復(fù)的子串個(gè)數(shù)（如HDU2222），則在累加之后將它們?nèi)恐脼?，防止下次再次累加。這一步操作實(shí)質(zhì)上就是統(tǒng)計(jì)A中所有以A[i]為右端點(diǎn)的子串個(gè)數(shù)。
這樣，整個(gè)過程就傻掉了。
代碼：
void solve()
{
int len = A.length(), x = root, y, c; res = 0;
re(i, len) {
c = A[i] - 97;
while (x && !T[x].ch[c]) x = T[x].fail;
if (!x) x = root; else x = T[x].ch[c];
y = x;
while (y) {res += T[y].mul; T[y].mul = 0; y = T[y].fail;}
}
}
有關(guān)例題：
【1】
HDU2222裸的多串匹配問題，模板題；
有關(guān)該題的詳細(xì)資料（包括易疵點(diǎn)）見
這里。
【2】
HDU2896比2222稍難一些，但還是模板題。注意這題的子串木有重復(fù)的，因此mul可以設(shè)為bool。
【3】
HDU3065統(tǒng)計(jì)每個(gè)子串出現(xiàn)的次數(shù)（可以重復(fù)），也是模板題。
以上三題均不卡空間。