AC自動(dòng)機(jī)

       算法目的：

       AC自動(dòng)機(jī)主要用于解決多模式串的匹配問(wèn)題，是字典樹(shù)(trie樹(shù))的變種，一種偽樹(shù)形結(jié)構(gòu)(主體是樹(shù)形的，但是由于加入了失敗指針，使得它變成了一個(gè)有向圖)；trie圖(我的理解^_^)是對(duì)AC自動(dòng)機(jī)的一種改造，使得圖中每個(gè)結(jié)點(diǎn)都有MAXC條出邊(MAXC表示該圖的字符集合大小), trie圖上的每個(gè)結(jié)點(diǎn)代表一個(gè)狀態(tài)，并且和AC自動(dòng)機(jī)的結(jié)點(diǎn)是一一對(duì)應(yīng)的。

       算法核心思想：

       學(xué)習(xí)AC自動(dòng)機(jī)(AC-Automan？艾斯奧特曼？-_-|||)之前，首先需要有字典樹(shù)和KMP的基礎(chǔ)，這是每一篇關(guān)于AC自動(dòng)機(jī)的文章都會(huì)論及的，所以我也就例行提一下。

       例如，有四個(gè)01字符串(模式串)，"01"、"10"、"110"、"11"，字符集合為{'0', '1'}。那么構(gòu)造trie圖分三步，首先建立字典樹(shù)，然后構(gòu)造失敗指針，最后通過(guò)失敗指針補(bǔ)上原來(lái)不存在的邊，那么現(xiàn)在就分三步來(lái)討論如何構(gòu)建一個(gè)完整的trie圖。

圖1

       1) 字典樹(shù)

       字典樹(shù)是一種樹(shù)形結(jié)構(gòu)，它將所有的模式串組織在一棵樹(shù)的樹(shù)邊上，它的根結(jié)點(diǎn)是一個(gè)虛根，每條樹(shù)邊代表一個(gè)字母，從根結(jié)點(diǎn)到任意一個(gè)結(jié)點(diǎn)的路徑上的邊的有序集合代表某個(gè)模式串的某個(gè)前綴。

       如圖1，綠色點(diǎn)為虛根，藍(lán)色點(diǎn)為內(nèi)部結(jié)點(diǎn)，紅色點(diǎn)為終止結(jié)點(diǎn)，即從根結(jié)點(diǎn)到終止結(jié)點(diǎn)的每條路徑代表了一個(gè)模式串，由于"11"是"110"的前綴，所以在圖中"11"這兩條邊是這兩個(gè)字符串路徑的共用部分，這樣就節(jié)省了存儲(chǔ)空間，由于trie樹(shù)的根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑(邊權(quán))都代表了一個(gè)模式串的前綴，所以它又叫前綴樹(shù)。

       字典樹(shù)實(shí)際上是一個(gè)DFA(確定性有限狀態(tài)自動(dòng)機(jī))，通常用轉(zhuǎn)移矩陣表示。行表示狀態(tài)，列表示輸入字符，(行, 列)位置表示轉(zhuǎn)移狀態(tài)。這種方式的查詢效率很高，但由于稀疏的現(xiàn)象嚴(yán)重，空間利用效率很低。所以一般采用壓縮的存儲(chǔ)方式即鏈表來(lái)表示狀態(tài)轉(zhuǎn)移，每個(gè)結(jié)點(diǎn)存儲(chǔ)至少兩個(gè)域：數(shù)據(jù)域data、子結(jié)點(diǎn)指針域next[MAXC](其中MAXC表示字符集總數(shù))。

       構(gòu)造字典樹(shù)的前提一般是給定一系列的模式串，然后對(duì)每個(gè)模式串進(jìn)行插入字典樹(shù)的操作，初始情況下字典樹(shù)只有一個(gè)虛根，如圖2所示，進(jìn)行四個(gè)模式串的插入后就完成了圖1中的字典樹(shù)的構(gòu)造，每次插入在末尾結(jié)點(diǎn)打上標(biāo)記(圖中紅色部分)，可以注意到，第四次操作實(shí)際上沒(méi)有生成新的結(jié)點(diǎn)，只是打了一個(gè)結(jié)尾標(biāo)記，由于它的這個(gè)性質(zhì)，使得字典樹(shù)的結(jié)點(diǎn)數(shù)目不會(huì)很多，大大壓縮了存儲(chǔ)結(jié)構(gòu)。具體實(shí)現(xiàn)方式和編碼會(huì)在下文中詳細(xì)講解。

圖2

       2) 失敗指針

       給定一個(gè)目標(biāo)串，要求在由模式串構(gòu)建的字典樹(shù)中查找這個(gè)目標(biāo)串中有多少個(gè)模式串，我們可以設(shè)定一個(gè)指針p，初始狀態(tài)下它指向根結(jié)點(diǎn)，然后從前往后枚舉目標(biāo)串，對(duì)每一個(gè)目標(biāo)串中的字符c，如果在p指向結(jié)點(diǎn)的出邊集合中能夠找到字符c對(duì)應(yīng)的邊，那么將p指向c對(duì)應(yīng)邊的子結(jié)點(diǎn)，循環(huán)往復(fù)，直到匹配失敗，那么退回到p結(jié)點(diǎn)的fail指針指向的結(jié)點(diǎn)繼續(xù)同樣的匹配，當(dāng)遇到一個(gè)終止結(jié)點(diǎn)時(shí)，計(jì)數(shù)器+1。

       這里的fail指針類(lèi)似KMP的next函數(shù)，每個(gè)trie結(jié)點(diǎn)都有一個(gè)fail指針，如圖3，首先將根結(jié)點(diǎn)的fail指針指向NULL，根結(jié)點(diǎn)的直接子結(jié)點(diǎn)的fail指針指向根結(jié)點(diǎn)，這一步是很顯然的，因?yàn)楫?dāng)一個(gè)字符都不能匹配的時(shí)候肯定是要跳到字符串首重新匹配了，每個(gè)結(jié)點(diǎn)的fail指針都是由它父結(jié)點(diǎn)的fail指針決定的，所以一次BFS就可以把所有結(jié)點(diǎn)的fail指針逐層求解出來(lái)了，具體實(shí)現(xiàn)方式和編碼會(huì)在下文中詳細(xì)講解。

圖3

       3) trie圖

       為了方便描述，我們先把所有trie樹(shù)上的結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)順序?yàn)榻Y(jié)點(diǎn)的插入順序，根結(jié)點(diǎn)編號(hào)為0。如圖4的第一個(gè)圖，我們發(fā)現(xiàn)如果現(xiàn)在是1號(hào)狀態(tài)(狀態(tài)即結(jié)點(diǎn))，當(dāng)接收一個(gè)'1'這個(gè)字符，那么它應(yīng)該進(jìn)入哪個(gè)狀態(tài)呢？答案很顯然，是2號(hào)狀態(tài)，因?yàn)檠刂址?/span>'1'的出邊到達(dá)的狀態(tài)正好是2號(hào)狀態(tài)；但是如果接受的是'0'字符，我們發(fā)現(xiàn)1號(hào)狀態(tài)沒(méi)有'0'字符代表的出邊，所以我們需要補(bǔ)上這條'0'邊，但是這條邊指向哪個(gè)狀態(tài)呢？答案是1號(hào)狀態(tài)的fail指針指向的狀態(tài)的'0'出邊對(duì)應(yīng)的狀態(tài)。我們發(fā)現(xiàn)這個(gè)狀態(tài)正好是它自己，所以向自己補(bǔ)一條邊權(quán)為'0'的邊(圖中的橙色邊，邊指向的結(jié)點(diǎn)稱為當(dāng)前狀態(tài)的后繼狀態(tài))。同樣是利用BFS的方式逐層求解所有結(jié)點(diǎn)的后繼狀態(tài)。我們發(fā)現(xiàn)所有結(jié)點(diǎn)遍歷完后，每個(gè)結(jié)點(diǎn)都有且僅有兩條出邊，這樣一個(gè)trie圖就誕生了。

圖4

       今后幾乎所有關(guān)于狀態(tài)機(jī)的問(wèn)題都是圍繞圖4的那個(gè)圖展開(kāi)的。

       新手初看算法的時(shí)候總是一頭霧水，即使看懂了也要花很大力氣才能把代碼寫(xiě)出來(lái)(至少我是這樣的)，所以沒(méi)有什么比直接闡述代碼更加直觀的了。

一、結(jié)構(gòu)定義

       對(duì)于trie樹(shù)上的每個(gè)結(jié)點(diǎn)，保存了以下數(shù)據(jù)域：

       1) 結(jié)點(diǎn)編號(hào) int id;

       每個(gè)結(jié)點(diǎn)的唯一標(biāo)識(shí)，用于狀態(tài)轉(zhuǎn)移的時(shí)候的下標(biāo)映射。

       2) 子結(jié)點(diǎn)指針 ACNode *next[MAXC];

       每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的個(gè)數(shù)就是字符串中字符集的大小，一般為26個(gè)英文字母，當(dāng)然也有特殊情況，比如說(shuō)和DNA有關(guān)的題，字符集為{ 'A'、'C'、'G'、'T' }，那么字符集大小就為4；和二進(jìn)制串有關(guān)的題，字符集大小就為2；而有的題則包含了所有的可見(jiàn)字符，所以字符集大小為256(有可能有中文字符...太BT了)，這個(gè)就要視情況而定了。

       3) 失敗指針 ACNode *fail;

       它的含義類(lèi)似KMP中的最長(zhǎng)前后綴的概念，即目標(biāo)串在trie樹(shù)上進(jìn)行匹配的時(shí)候，如果在P結(jié)點(diǎn)上匹配失敗，那么應(yīng)該跳到P->fail繼續(xù)匹配，如果還是失敗，那么跳到P->fail->fail繼續(xù)匹配，對(duì)于這個(gè)fail指針的構(gòu)造，下文會(huì)詳細(xì)講解，這里先行跳過(guò)。

       4) 結(jié)尾標(biāo)記 int cnt, val;

       每個(gè)模式串在進(jìn)行插入的過(guò)程中，會(huì)對(duì)模式串本身進(jìn)行一次線性的遍歷，當(dāng)遍歷完畢即表示將整個(gè)串插入完畢，在結(jié)尾結(jié)點(diǎn)需要一個(gè)標(biāo)記，表示它是一個(gè)模式串的末尾，有些問(wèn)題會(huì)出現(xiàn)多個(gè)相同的模式串，所以用cnt來(lái)表示該串出現(xiàn)的次數(shù)，每插入一次對(duì)cnt進(jìn)行一次自增；而有的題中，相同的模式串有不同的權(quán)值，并且模式串的個(gè)數(shù)較少(<= 15)，那么可以將該結(jié)點(diǎn)是否是模式串的末尾用2的冪來(lái)表示，壓縮成二進(jìn)制的整數(shù)記錄在val上(例如當(dāng)前結(jié)點(diǎn)是第二個(gè)模式串和第四個(gè)模式串的結(jié)尾，則val = (1010)₂)。

       終于看到故事的主角(ACAutoman, 艾斯奧特曼)了，同樣介紹一下它需要維護(hù)的數(shù)據(jù)結(jié)構(gòu)：

       1) 結(jié)點(diǎn)緩存 ACNode* nodes[MAXQ];

       為了方便訪問(wèn)，我們將所有的結(jié)點(diǎn)組織在一個(gè)數(shù)組中，并且一開(kāi)始不開(kāi)辟空間，每次需要一個(gè)結(jié)點(diǎn)的時(shí)候，利用接口getNode()獲取，類(lèi)似內(nèi)存池的概念，避免頻繁申請(qǐng)和釋放內(nèi)存時(shí)候的時(shí)間開(kāi)銷(xiāo)。

       2) 根結(jié)點(diǎn)指針ACNode *root;

       trie樹(shù)，既然是樹(shù)，自然是有一個(gè)根結(jié)點(diǎn)的嘛。

       3) 結(jié)點(diǎn)總數(shù) int nodeCount;

       4) 結(jié)點(diǎn)隊(duì)列 ACNodeQueue Q;

       ACNodeQueue是自己實(shí)現(xiàn)的一個(gè)隊(duì)列，數(shù)據(jù)域?yàn)?/span>ACNode *，主要是因?yàn)?/span>STL的效率實(shí)在不敢恭維，在某些OJ上效率極低，自己封裝一套比較好，這個(gè)隊(duì)列會(huì)在BFS的時(shí)候求失敗指針時(shí)用到。

二、模式串插入

       str為模式串，將它插入到trie樹(shù)時(shí)，需要進(jìn)行一次線性遍歷，為了使每個(gè)字符訪問(wèn)方便，我們將字母映射到整數(shù)區(qū)間[0, IDSize)中，只要采用最簡(jiǎn)單的哈希即可。初始化當(dāng)前結(jié)點(diǎn)p為根結(jié)點(diǎn)，對(duì)于字符串的某個(gè)字符，轉(zhuǎn)換成整數(shù)id后，檢測(cè)當(dāng)前結(jié)點(diǎn)p是否存在id這個(gè)子結(jié)點(diǎn)，如果不存在則利用getNode()獲取一個(gè)新的結(jié)點(diǎn)，并且讓當(dāng)前結(jié)點(diǎn)p的id子結(jié)點(diǎn)指向它，然后將當(dāng)前結(jié)點(diǎn)轉(zhuǎn)到它的id子結(jié)點(diǎn)上，繼續(xù)上述操作。直到整個(gè)模式串枚舉完畢，在結(jié)點(diǎn)p打上結(jié)束標(biāo)記即可。

三、失敗指針、trie圖 構(gòu)造

       首先，講一下失敗指針的含義，因?yàn)橹疤岬?，一個(gè)模式串的某個(gè)字符匹配失敗的時(shí)候，就跳到它的失敗指針上繼續(xù)匹配，重復(fù)上述操作，直到這個(gè)字符匹配成功，所以失敗指針一定滿足一個(gè)性質(zhì)，它指向的一定是某個(gè)串的前綴，并且這個(gè)前綴是當(dāng)前結(jié)點(diǎn)所在前綴的后綴，而且一定是最長(zhǎng)后綴。仔細(xì)理解一下這句話，首先，一定是某個(gè)串的前綴，這是顯然的，因?yàn)?/span>trie樹(shù)本來(lái)就是前綴樹(shù)，它的任意一個(gè)結(jié)點(diǎn)都是某個(gè)模式串的前綴；然后再來(lái)看后面一句話，為了讓當(dāng)前字符能夠找到匹配，那么當(dāng)前結(jié)點(diǎn)的某個(gè)后綴必須要和某個(gè)模式串的前綴相匹配，這個(gè)性質(zhì)就和KMP的next數(shù)組不謀而合了。

       然后，就是來(lái)看如何利用BFS求出所有結(jié)點(diǎn)的失敗指針了。

       1) 對(duì)于根結(jié)點(diǎn)root的失敗指針，我們將它直接指向NULL，對(duì)于根結(jié)點(diǎn)下所有的子結(jié)點(diǎn)，失敗指針一定是指向root的，因?yàn)楫?dāng)一個(gè)字符都不能匹配的時(shí)候，自然也就不存在更短的能夠與之匹配的前綴了；

       2) 將求完失敗指針的結(jié)點(diǎn)插入隊(duì)列中；

       3) 每次彈出一個(gè)結(jié)點(diǎn)now，詢問(wèn)它的每個(gè)字符對(duì)應(yīng)的子結(jié)點(diǎn)，為了闡述方便，我們將now的i號(hào)子結(jié)點(diǎn)記為now->next[i]：

              a) 如果now->next[i]為NULL，那么將now->next[i]指向now的失敗指針的i號(hào)子結(jié)點(diǎn), 即 now->next[i] = now->fail->next[i];

              b) 如果now->next[i]不等于NULL，則需要構(gòu)造now->next[i]的失敗指針，由于a)的操作，我們知道now的失敗指針一定存在一個(gè)i號(hào)子結(jié)點(diǎn)，即now->fail->next[i]，那么我們將now->next[i]的失敗指針指向它，即now->next[i]->fail = now->fail->next[i]；

       4) 重復(fù)2)的操作直到隊(duì)列為空；

四、目標(biāo)串匹配

       對(duì)目標(biāo)串進(jìn)行匹配的時(shí)候，同樣需要掃描目標(biāo)字符串。由于trie圖已經(jīng)創(chuàng)建完畢，每個(gè)結(jié)點(diǎn)讀入一個(gè)字符的時(shí)候都能夠進(jìn)入到下一個(gè)狀態(tài)，所以我們只需要根據(jù)目標(biāo)串給定的字符進(jìn)行遍歷，然后每次檢查當(dāng)前的結(jié)點(diǎn)是否是結(jié)尾結(jié)點(diǎn)，當(dāng)然還需要檢查p的失敗指針指向的結(jié)點(diǎn)...累加所有的cnt和即為模式串的個(gè)數(shù)。

        對(duì)于AC自動(dòng)機(jī)，各大OJ都有相關(guān)習(xí)題，來(lái)看幾道比較經(jīng)典的：

HDU 2222 Keywords Search

題意：給定N(N <= 10000)個(gè)長(zhǎng)度不大于50的模式串，再給定一個(gè)長(zhǎng)度為L(L <= 10⁶)目標(biāo)串，求目標(biāo)串出現(xiàn)了多少個(gè)模式串。

題解：AC自動(dòng)機(jī)模板題，在每個(gè)trie結(jié)點(diǎn)存儲(chǔ)一個(gè)count值，每次插入一個(gè)單詞的時(shí)候?qū)卧~結(jié)尾結(jié)點(diǎn)的count值進(jìn)行自增(不能將count值直接置為1，因?yàn)橛锌赡苣Ｊ酱杏卸鄠€(gè)相同的串，它們是要被算作多次的)，然后在詢問(wèn)的時(shí)候，每次計(jì)數(shù)完畢之后，將count值標(biāo)為-1表示它已經(jīng)被計(jì)算過(guò)了。最后輸出所有count的累加和即可。

HDU 2896 病毒侵襲

題意：N(N <= 500)個(gè)長(zhǎng)度不大于200的模式串(保證所有的模式串都不相同)，M(M <= 1000)個(gè)長(zhǎng)度不大于10000的待匹配串，問(wèn)待匹配串中有哪幾個(gè)模式串，題目保證每個(gè)待匹配串中最多有三個(gè)模式串。

題解：構(gòu)造trie樹(shù)和fail指針，由于每個(gè)模式串都不同，所以每個(gè)代表模式串結(jié)尾的trie結(jié)點(diǎn)存儲(chǔ)模式串對(duì)應(yīng)的編號(hào)idx，掃描所有帶匹配串，對(duì)于每個(gè)待匹配串利用失敗指針模擬匹配，匹配的模式串個(gè)數(shù)到達(dá)三個(gè)的時(shí)候放棄掃描該串。

可見(jiàn)字符包括空格，所以讀入的時(shí)候需要用gets()，子結(jié)點(diǎn)個(gè)數(shù)為128。

HDU 3065 病毒侵襲持續(xù)中

題意：N(N <= 1000)個(gè)長(zhǎng)度不大于50的模式串(保證所有的模式串都不相同)，一個(gè)長(zhǎng)度不大于2000000的待匹配串，求模式串在待匹配串中的出現(xiàn)次數(shù)。

題解：由于每個(gè)病毒串不會(huì)完全相同，對(duì)于每個(gè)病毒串末尾記錄一個(gè)編號(hào)標(biāo)記，完全匹配后對(duì)編號(hào)對(duì)應(yīng)的數(shù)組進(jìn)行累加和計(jì)算。

PKU 1204 Word Puzzles

題意：給定一個(gè)L x C(C <= 1000, L <= 1000)的字母矩陣，再給定W(W <= 1000)個(gè)字符串，保證這些字符串都會(huì)在字母矩陣中出現(xiàn)(8種方向)，求它們的出現(xiàn)位置和方向。

題解：先緩存所有數(shù)據(jù)，然后對(duì)W個(gè)字符串建立字典樹(shù)和失敗指針，再掃描字母矩陣所有8個(gè)方向的字符串進(jìn)行匹配。

ZJY 3228 Searching the String

       題意：給定一個(gè)長(zhǎng)度為N(N <= 10⁵)的目標(biāo)串，然后再給定M(M <= 10⁵)個(gè)長(zhǎng)度不大于6的字符串，問(wèn)這些字符串在目標(biāo)串的出現(xiàn)次數(shù)(分可重疊和不可重疊兩種)。

       題解：將M個(gè)串作為模式串建立自動(dòng)機(jī)，對(duì)于可重疊的情況直接詢問(wèn)即可，類(lèi)似HDU 3065，不可重疊的情況需要記錄每個(gè)串的長(zhǎng)度L_i以及之前這個(gè)串匹配到的最大位置P_i，對(duì)于當(dāng)前位置Pos，如果P_i + L_i <= Pos，那么認(rèn)為和之前的一次匹配沒(méi)有重疊，計(jì)數(shù)累加，并且更新P_i = Pos。

為了方便，我把兩種計(jì)算方式的模式串分別建立了兩個(gè)自動(dòng)機(jī)。

PKU 3208 Apocalypse Someday

題意：求第K(K <= 5*10⁷)個(gè)有連續(xù)3個(gè)6的數(shù)。

題解：建立DFA如下圖，其中0為初態(tài)，1為非法狀態(tài)(存在前導(dǎo)0)，2為后綴沒(méi)有6的狀態(tài)，3、4、5分別為后綴有1個(gè)、2個(gè)、3個(gè)6的狀態(tài)，所以5為接收態(tài)，因?yàn)橐坏┏霈F(xiàn)了3個(gè)6，那么無(wú)論接下來(lái)的是什么數(shù)都認(rèn)為是合法數(shù)。

既然有了狀態(tài)轉(zhuǎn)移圖就可以輕松地利用狀態(tài)轉(zhuǎn)移方程求出長(zhǎng)度為n有連續(xù)3個(gè)6的數(shù)字的個(gè)數(shù)，當(dāng)長(zhǎng)度小于等于L的滿足條件的數(shù)字總數(shù)大于等于K的時(shí)候，就表明第K個(gè)滿足條件的數(shù)字的長(zhǎng)度為L，然后枚舉每一位的數(shù)字判可行即可。

PKU 2778 DNA Sequence

題意：給定m(m <= 10)個(gè)DNA片段，每個(gè)串長(zhǎng)度不超過(guò)10。求長(zhǎng)度為N(N <= 2*10⁹)的串中不包括任何給定的DNA片段的串的總數(shù)。

題解：利用模式串建立trie圖，將trie圖轉(zhuǎn)化為矩陣表示，利用二分求冪加速。

為了更加直觀，舉例說(shuō)明：

例如，m=2，兩個(gè)DNA片段分別為A和CAG，可以建立如下AC自動(dòng)機(jī)：

圖5

其中，灰色箭頭代表樹(shù)邊，虛線代表失敗指針，藍(lán)色結(jié)點(diǎn)代表終止?fàn)顟B(tài)，0為起始狀態(tài)。

然后我們利用它來(lái)構(gòu)造trie圖，如圖6。

圖6

構(gòu)造方法是利用BFS，依次處理每個(gè)狀態(tài)可以到達(dá)哪些狀態(tài)，建立可達(dá)矩陣。

具體步驟如下：

1) 初始狀態(tài)入隊(duì)。

2) 每次彈出一個(gè)狀態(tài)結(jié)點(diǎn)進(jìn)行處理，直到隊(duì)列為空。

a) 對(duì)于當(dāng)前處理的結(jié)點(diǎn)P，判斷P是否是一個(gè)終止結(jié)點(diǎn)，如果不是，則判斷P的fail指針指向的是否是一個(gè)終止結(jié)點(diǎn)，一直迭代到fail指針為空，如果迭代過(guò)程中找到某個(gè)結(jié)點(diǎn)為終止結(jié)點(diǎn)，那么表示P所在串的某個(gè)后綴包含了給定的DNA片段，那么標(biāo)記P為終止結(jié)點(diǎn)，重復(fù)2)，否則轉(zhuǎn)b)。

b) 枚舉P的所有子結(jié)點(diǎn)Q[i](這里的子結(jié)點(diǎn)是包含所有字符集的)：

i) 如果Q[i]這個(gè)結(jié)點(diǎn)不為空，那么DFA[P][Q[i]] ++，Q[i]入隊(duì)；

ii) 否則沿著P的fail指針一直找，直到找到一個(gè)結(jié)點(diǎn)S的對(duì)應(yīng)子結(jié)點(diǎn)T[i]不為空，那么DFA[P][T[i]]++，如果一直找不到，那么DFA[P][root]++;

當(dāng)隊(duì)列為空的時(shí)候，有限狀態(tài)自動(dòng)機(jī)也就構(gòu)造完畢了，按照這種方式，我們可以發(fā)現(xiàn)，除了終止?fàn)顟B(tài)，所有狀態(tài)都有四條出邊(A、C、G、T)，但是終止?fàn)顟B(tài)并非真正意義上的終止?fàn)顟B(tài)，于是我們?cè)诮K止?fàn)顟B(tài)上添加四條回邊(指向自己)，表示如果狀態(tài)進(jìn)入了終止?fàn)顟B(tài)就再也出不去了，這樣一來(lái)，這個(gè)狀態(tài)機(jī)就完整了，任意一個(gè)狀態(tài)只要接收A、C、G、T四個(gè)字符中的一個(gè)就能進(jìn)入下一個(gè)狀態(tài)，這樣就轉(zhuǎn)化成了一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，假設(shè)狀態(tài)方程DP[i][j]表示長(zhǎng)度為i的串在j狀態(tài)下的字符串個(gè)數(shù)，那么對(duì)于圖2的狀態(tài)機(jī)，有如下關(guān)系：

DP[i][0] = 2 * DP[i-1][2] + 2 * DP[i-1][0];

DP[i][1] = DP[i-1][0] + 4 * DP[i-1][1];

DP[i][2] = DP[i-1][0] + DP[i-1][2];

DP[i][3] = DP[i-1][2] + 4*DP[i-1][3];

由于在DFA狀態(tài)處理的時(shí)候3號(hào)狀態(tài)為終止?fàn)顟B(tài)，所以DP[i][4]其實(shí)已經(jīng)是一個(gè)冗余狀態(tài)了，所以不列入討論范圍。

按照遞推方程，DP[N][0] + DP[N][2]就是我們要求的答案，但是N很大，所以可以將DP轉(zhuǎn)移轉(zhuǎn)化成矩陣，即：

然后利用矩陣的二分求冪來(lái)加速了。

這題更加直觀的理解是：從起點(diǎn)0開(kāi)始，走N步，經(jīng)過(guò)的路徑就是一個(gè)DNA串，如果最后到達(dá)的是終止?fàn)顟B(tài)，那么表示它包含了m個(gè)DNA片段中的至少一個(gè)。所有路徑長(zhǎng)度為N，終點(diǎn)非終止?fàn)顟B(tài)的路徑數(shù)目之和就是我們要求的解。

PKU 1625 Censored!

題意：給定p(p <= 10)個(gè)長(zhǎng)度不大于10的模式串，求長(zhǎng)度為m(m <= 50)的串中不包含任何模式串的串的種類(lèi)數(shù)。

題解：首先利用模式串建立trie圖，用DP[i][j]表示長(zhǎng)度為i，狀態(tài)為j的字符串的種類(lèi)數(shù)，枚舉所有字符進(jìn)行狀態(tài)轉(zhuǎn)移即可。最后Sum{DP[m][i], i表示非終止?fàn)顟B(tài)} 就是答案，這題如果將字符直接進(jìn)行下標(biāo)映射，有可能會(huì)RE，就是它的字符的ASCII碼有可能是在128-255之間的(例如中文)，如果用scanf讀入，轉(zhuǎn)換成char就變成了負(fù)數(shù)，如果映射到下標(biāo)就RE了，所以在映射之前最好先轉(zhuǎn)成unsigned char。

PKU 3691 DNA repair

       題意：給定N(N <= 50)個(gè)長(zhǎng)度不超過(guò)20的模式串，再給定一個(gè)長(zhǎng)度為M(M <= 1000)的目標(biāo)串S，求在目標(biāo)串S上最少改變多少字符，可以使得它不包含任何的模式串（所有串只有ACGT四種字符）。

       題解：利用模式串建立trie圖，trie圖的每個(gè)結(jié)點(diǎn)(即下文講到的狀態(tài)j)維護(hù)三個(gè)結(jié)構(gòu)，

Node{

       Node *next[4];   // 能夠到達(dá)的四個(gè)狀態(tài) 的結(jié)點(diǎn)指針

       int  id;         // 狀態(tài)ID，用于到數(shù)組下標(biāo)的映射

       int  val;        // 當(dāng)前狀態(tài)是否是一個(gè)非法狀態(tài) （以某些模式串結(jié)尾）

}

用DP[i][j]表示長(zhǎng)度為i (i <= 1000)，狀態(tài)為j(j <= 50*20 + 1)的字符串變成目標(biāo)串S需要改變的最少字符，設(shè)初始狀態(tài)j = 0，那么DP[0][0] = 0，其它的DP[i][j]均為無(wú)窮大。從長(zhǎng)度i到i+1進(jìn)行狀態(tài)轉(zhuǎn)移，每次轉(zhuǎn)移枚舉共四個(gè)字符(A、C、G、T)，如果枚舉到的字符和S對(duì)應(yīng)位置相同則改變值T=0，否則T=1；那么有狀態(tài)轉(zhuǎn)移方程 DP[i][j] = Min{ DP[i-1][ fromstate ] + T, fromstate為所有能夠到達(dá)j的狀態(tài) };最后DP[n][j]中的最小值就是答案。

PKU 1699 Best Sequence

       題意：給定N(N <= 10)個(gè)長(zhǎng)度不超過(guò)20的模式串，求一個(gè)長(zhǎng)度最短的串使得它包含所有的模式串。

       題解：利用模式串建立trie圖，trie圖的每個(gè)結(jié)點(diǎn)維護(hù)一個(gè)二進(jìn)制權(quán)值，(val & 2ⁱ)不為0表示從根結(jié)點(diǎn)到該結(jié)點(diǎn)的某條路徑上有第i個(gè)模式串，用DP[i][j]表示狀態(tài)為i，模式串的二進(jìn)制組合為j的最短串的長(zhǎng)度，初始化DP[0][0] = 0，然后就轉(zhuǎn)化成了一個(gè)在trie圖上求(0, 0)到(i, 2ⁿ-1)點(diǎn)的最短路問(wèn)題，最后求出來(lái)的DP[i][2ⁿ-1] (i < 200, 最多200個(gè)結(jié)點(diǎn)) 的最小值就是答案。

       注意：本題中的模式串有重復(fù)的情況需要特殊處理。

HDU 2296 Ring

題意：給定N (N <= 50) 和M(M <= 100)個(gè)長(zhǎng)度不超過(guò)10的字符串以及每個(gè)字符串的權(quán)值H_i，求一個(gè)長(zhǎng)度不超過(guò)N的字符串使得她包含的權(quán)值最大，如果有多個(gè)解輸出長(zhǎng)度最短的，如果還是有多個(gè)解，輸出字典序最小的。

題解：利用模式串建立trie圖，用DP[i][j]表示長(zhǎng)度為i，處于j狀態(tài)下的字符串的最大權(quán)值，然后枚舉26個(gè)字符進(jìn)行狀態(tài)轉(zhuǎn)移，轉(zhuǎn)移的過(guò)程中需要記錄每個(gè)狀態(tài)的前驅(qū)，每次進(jìn)行最大值比較的時(shí)候，遇到最大值相等的情況則需要回溯，取字典序最小的。

HDU 2825 Wireless Password

       題意：給定m(m <= 10)個(gè)長(zhǎng)度不大于10的模式串，求長(zhǎng)度為n(n <= 25)的至少包含k個(gè)模式串的字符串的種數(shù)，答案模上20090717。

       題解：類(lèi)似PKU 1699利用模式串建立trie圖，trie圖上每個(gè)結(jié)點(diǎn)表示為一個(gè)狀態(tài)，第i個(gè)模式串的權(quán)值為2ⁱ。用DP[i][j][l]表示長(zhǎng)度為i，狀態(tài)為j，已經(jīng)有t個(gè)模式串的種類(lèi)數(shù)（其中l表示這t個(gè)模式串的權(quán)值的位或），那么對(duì)于每個(gè)狀態(tài)j，輸入’a-z’這26個(gè)字符后必定能夠到達(dá)下一個(gè)狀態(tài)，從DP[0][0][0]=1開(kāi)始迭代計(jì)算，最終SUM { DP[n][j][s] , s的二進(jìn)制表示中1的個(gè)數(shù)大于等于k}就是答案。

HDU 3341 Lost 's revenge

題意：給定N(N <= 50)個(gè)長(zhǎng)度不超過(guò)10的模式串(ACGT串)，再給定一個(gè)長(zhǎng)度為M(M <= 40)的目標(biāo)串S，求將目標(biāo)串重排列，使得它包含最多的模式串，求這個(gè)最多的數(shù)目。

題解：利用模式串建立trie圖，trie圖上最多有500個(gè)結(jié)點(diǎn)( N*10 )，然后樸素的思想就是用S(i, i_A, i_C, i_G, i_T)表示在i狀態(tài)下，擁有i_A個(gè)A、i_C個(gè)C、i_G個(gè)G、i_T個(gè)T的串擁有的最多的模式串的個(gè)數(shù)，但是i_A, i_C, i_G, i_T的取值均是[0, 40]，所以我們需要把狀態(tài)壓縮一下，我們知道當(dāng)四種字符都取10的時(shí)候可以讓狀態(tài)數(shù)達(dá)到最大，即11⁴ = 14641, 所以可以令Max_A、

Max_C、Max_G、Max_T分別表示四種字符出現(xiàn)的個(gè)數(shù)，那么T字符的權(quán)值為1，G字符的權(quán)值為(Max_T + 1)，C字符的權(quán)值為(Max_G + 1) *(Max_T + 1)，A字符的權(quán)值為(Max_C + 1) *(Max_G + 1) *(Max_T + 1)，進(jìn)行進(jìn)制壓縮之后總的狀態(tài)數(shù)不會(huì)超過(guò)11⁴,可以用DP[i][j]表示在trie的i號(hào)結(jié)點(diǎn)時(shí)ACGT四個(gè)字符個(gè)數(shù)的壓縮狀態(tài)為j時(shí)的字符串包含模式串的最多數(shù)目，然后就是進(jìn)行O(4*500*11⁴)的狀態(tài)轉(zhuǎn)移了。

HDU 2243 考研路茫茫——單詞情結(jié)

題意：給定N(N < 6)個(gè)長(zhǎng)度不超過(guò)5的單詞，求包含至少一個(gè)單詞并且長(zhǎng)度不超過(guò)L(L < 2³¹)的字符串的種數(shù)。

題解：利用PKU 2778的方法構(gòu)造矩陣，由于求的是長(zhǎng)度不超過(guò)L的種數(shù)，即長(zhǎng)度為1、2、3...L，假設(shè)原有矩陣為M，那么構(gòu)造一個(gè)新的矩陣M'，它由兩個(gè)原矩陣M，一個(gè)零矩陣O和一個(gè)單位陣I構(gòu)成：

該矩陣的右上角的子矩陣就是我們所求的方案矩陣，然后對(duì) M' 二分求冪即可。這里需要總數(shù)模2⁶⁴，利用補(bǔ)碼的性質(zhì)，可以直接聲明unsigned __int64直接運(yùn)算即可，不需要用到大數(shù)。

HDU 3247 Resource Archiver

       題意：給定n(n <= 10)個(gè)長(zhǎng)度小于等于1000的源字符串以及m(m <= 1000)個(gè)病毒串(所有病毒串總長(zhǎng)度不超過(guò)50000)，求一個(gè)串使得它包含所有的源字符串并且不包含任何一個(gè)病毒串，求這個(gè)字符串的最短長(zhǎng)度(所有的串保證都是01串)。

       題解：PKU 1699的加強(qiáng)版。

PKU 4052 Hrinity

題意：給定n(n <= 2500)個(gè)長(zhǎng)度小于等于1100的模式串，求長(zhǎng)度不大于5100000的目標(biāo)串S中包含的模式串的數(shù)目，如果包含了模式串A和B，并且B是A的子串，那么只記錄A。

題解：建立trie圖，每個(gè)字符串結(jié)尾標(biāo)記記錄模式串編號(hào)，進(jìn)行目標(biāo)串匹配的時(shí)候，利用哈希將所有是目標(biāo)串子串的模式串標(biāo)記為1，然后枚舉所有標(biāo)記過(guò)的模式串，對(duì)他們進(jìn)行模式匹配，利用同樣的方法將模式串的所有模式串子串標(biāo)記為0，最后統(tǒng)計(jì)有多少個(gè)模式串的標(biāo)記為1就是答案了。