文不達(dá)意挑围，口齒不清蜘矢，思想混亂，令人噴飯。（估計(jì)只有我自己才能看懂我在說(shuō)什么）簡(jiǎn)書(shū)沒(méi)有mathjax公式?jīng)]法愉快顯示
AC自動(dòng)機(jī)(Aho-Corasick Automaton)是一個(gè)依次輸入一個(gè)字符串S的各個(gè)字符兔毙，僅當(dāng)AC自動(dòng)機(jī)中保存的字符串出現(xiàn)在當(dāng)前串S當(dāng)中時(shí)，進(jìn)入合法狀態(tài)的自動(dòng)機(jī)芜茵。AC自動(dòng)機(jī)被構(gòu)建在一棵Trie樹(shù)上寺鸥。我們可以像使用KMP算法時(shí)一樣笆载，對(duì)節(jié)點(diǎn)構(gòu)造Fail指針腻要，實(shí)現(xiàn)線性時(shí)間復(fù)雜度的字符串匹配功能咳短。
基礎(chǔ)內(nèi)容
AC自動(dòng)機(jī)被構(gòu)建在Trie樹(shù)上，節(jié)點(diǎn)有Fail指針〔愎考慮Fail指針的性質(zhì)毁菱，F(xiàn)ail指針只有可能是如下幾種情況中的一種：
- Fail指向Trie樹(shù)的根節(jié)點(diǎn)
- Fail指向父節(jié)點(diǎn)開(kāi)始的由Fail指針構(gòu)成的鏈上某個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)
如何理解這條性質(zhì)呢？當(dāng)Trie樹(shù)上同時(shí)有串ABCE和BCD物喷，對(duì)于目標(biāo)串ABCD進(jìn)行字符串匹配的時(shí)候宠进，AC自動(dòng)機(jī)讀入目標(biāo)串中D的時(shí)候堤器，發(fā)現(xiàn)和ABCE中的E不同拱撵，于是跳轉(zhuǎn)到BCD中的D進(jìn)行匹配。所以除了父節(jié)點(diǎn)的Fail指針指向根節(jié)點(diǎn)的情況外，節(jié)點(diǎn)的Fail指針滿足上面的性質(zhì)妆距。于是有了構(gòu)造Fail指針的辦法：
/**
* 約定：
* CodeSet: 字符集，比如字母就是'a'~'z'
* trie[u][i]: Trie樹(shù)的邊，u為節(jié)點(diǎn)編號(hào)蓬推，i為下一個(gè)字符，我們將一些額外的邊（匹配之用）也會(huì)存進(jìn)去
* fail[u]: 失敗指針糕珊，指向一個(gè)節(jié)點(diǎn)編號(hào)
* root: 根節(jié)點(diǎn)編號(hào)毅糟，這里設(shè)置為0
*/
void makeFail(int u) {
for (int i: codeSet) {
if (trie[u][i]!=null) {
int tmp=fail[u];
while (tmp!=root&&trie[tmp][i]==null)
tmp=fail[tmp];
fail[trie[u][i]]=(u==root)?0:trie[tmp][i];
}else {
trie[u][i]=trie[fail[u]][i]; // 將不存在的子節(jié)點(diǎn)指向fail指針引導(dǎo)的狀態(tài)
}
}
}
構(gòu)造Fail指針需要遵從一定的順序，顯然DFS是不可以的喇肋。因?yàn)樗褜ail指針的時(shí)候间学，有的節(jié)點(diǎn)（例如相鄰子樹(shù)上的節(jié)點(diǎn)）Fail指針沒(méi)有計(jì)算出來(lái)氮采，所以無(wú)法推算。在這種時(shí)候應(yīng)當(dāng)用BFS進(jìn)行搜尋。
在上面構(gòu)建Fail指針的時(shí)候我們還進(jìn)行了另外一種操作：就是將”不存在的子節(jié)點(diǎn)“指向了Fail指針引導(dǎo)的子節(jié)點(diǎn)忿磅。在這樣的一張有向圖上我們就可以輕松地進(jìn)行字符串匹配了糯彬。
字符串匹配
就像KMP算法一樣，AC自動(dòng)機(jī)對(duì)字符串的匹配也是逐個(gè)讀入字符葱她，比對(duì)并進(jìn)行狀態(tài)轉(zhuǎn)移（在上文提到的生成的有向圖中）撩扒。當(dāng)遇到合法節(jié)點(diǎn)的時(shí)候，我們進(jìn)行計(jì)數(shù)览效。下面看這樣的例子：在ABCDEF中查找ABC和BC的過(guò)程
- 依次讀入ABC却舀，AC自動(dòng)機(jī)從根結(jié)點(diǎn)開(kāi)始由A->B->C進(jìn)行轉(zhuǎn)移，我們發(fā)現(xiàn)ABC被成功匹配了锤灿。當(dāng)讀取D的時(shí)候挽拔，狀態(tài)被轉(zhuǎn)移到了根節(jié)點(diǎn)，因?yàn)闆](méi)有字符能和D匹配
- 直到讀完原字符串為止
問(wèn)題：BC沒(méi)有被匹配到但校。實(shí)際上在進(jìn)入合法節(jié)點(diǎn)的時(shí)候螃诅，合法節(jié)點(diǎn)Fail指針形成的鏈上，所有的合法節(jié)點(diǎn)均被匹配上了状囱。實(shí)際統(tǒng)計(jì)匹配成功數(shù)時(shí)术裸，我們可以只在該節(jié)點(diǎn)上計(jì)數(shù)。在統(tǒng)計(jì)完畢之后亭枷，將Fail指針形成的樹(shù)做一次樹(shù)形dp：節(jié)點(diǎn)的匹配數(shù)等于子樹(shù)根節(jié)點(diǎn)匹配數(shù)之和來(lái)計(jì)算總匹配數(shù)袭艺。
題目
AC自動(dòng)機(jī)的題目形式相對(duì)固定，雖然不會(huì)出特別裸的字符串匹配題目叨粘。
AC自動(dòng)機(jī)在ACM賽場(chǎng)上出現(xiàn)一般會(huì)作為引出題目的狀態(tài)轉(zhuǎn)移猾编、或者模型的工具。AC自動(dòng)機(jī)的作用可以歸結(jié)如下：
- 字符串匹配（HDU3065）
- 字符串計(jì)數(shù)
- 字符串構(gòu)造（引出模型）
HDU5955 一個(gè)骰子不停的扔升敲，扔出誰(shuí)的目標(biāo)序列誰(shuí)就贏了答倡，問(wèn)：每個(gè)人獲勝的概率。其中每個(gè)人對(duì)應(yīng)一種目標(biāo)序列（由1~6中的整數(shù)構(gòu)成驴党，且一局游戲中每個(gè)人的序列長(zhǎng)度相等而不同）瘪撇。
對(duì)所有人的獲勝序列構(gòu)造AC自動(dòng)機(jī)。AC自動(dòng)機(jī)中可以得到扔骰子的狀態(tài)轉(zhuǎn)移過(guò)程：實(shí)際上AC自動(dòng)機(jī)中某個(gè)節(jié)點(diǎn)包含了之前扔的幾次的信息（比如說(shuō)從Trie樹(shù)的根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的字符構(gòu)成的串，這些信息往往很有用倔既；又比如說(shuō)節(jié)點(diǎn)是否是游戲的終止?fàn)顟B(tài)——最后幾次的結(jié)果和某個(gè)人的串對(duì)應(yīng)恕曲，游戲結(jié)束）。對(duì)于自動(dòng)機(jī)中某個(gè)節(jié)點(diǎn)u叉存，它能轉(zhuǎn)移到的節(jié)點(diǎn)（后繼）v_i一共有6個(gè)（很顯然扔一個(gè)立方體骰子能產(chǎn)生6個(gè)不同的數(shù)字之一）码俩，到達(dá)該節(jié)點(diǎn)的概率就等于sum_{1}^{6}P(v_i)/6。根據(jù)這個(gè)構(gòu)造出增量矩陣A：AC自動(dòng)機(jī)中有邊u->v（u不是游戲結(jié)束狀態(tài)）歼捏，那么u行v列被設(shè)置為1/6。假設(shè)答案是b（n維列矩陣笨篷，記錄了自動(dòng)機(jī)每個(gè)節(jié)點(diǎn)狀態(tài)的概率）瞳秽， 初始序列是x（除了0節(jié)點(diǎn)概率為1之外其它都是0）。有
b=sum_{i=1}{inf}(Ai)x
當(dāng)上式收斂時(shí)率翅，將它改寫(xiě)為b=(E-A)^{-1}x练俐，即(E-A)b=x，接下來(lái)的任務(wù)就是用高斯消元求解b冕臭。b中所有結(jié)束狀態(tài)的概率即為所求答案腺晾。
很可惜在下并沒(méi)有弄清楚題目背后的數(shù)學(xué)原理
POJ2778 有m種DNA序列是有疾病的，問(wèn)有多少種長(zhǎng)度為n的DNA序列不包含任何一種有疾病的DNA序列辜贵。（僅含A,T,C,G四個(gè)字符）
- m=4,n=3,{“AA”,”AT”,”AC”,”AG”}悯蝉，答案為36，表示有36種長(zhǎng)度為3的序列可以不包含疾病
- 疾病字符串最多10個(gè)托慨，且長(zhǎng)度<=10
很慚愧……等我研究懂了再說(shuō)
