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