AC自動(dòng)機(jī)構(gòu)造

1、自動(dòng)機(jī)的構(gòu)造雅禮 朱全民字典樹(shù)（trie） 當(dāng)關(guān)鍵字是串的時(shí)候，往往用trie。我們的動(dòng)機(jī)是：利用串的公共前綴來(lái)節(jié)約內(nèi)存，加快檢索速度。 例如，需要保存“computer”和“command”，由于它們的前三個(gè)字母是相同的，所以希望它們共享前三個(gè)字母，而只有剩下部分才進(jìn)行分開(kāi)儲(chǔ)存。例如，需要保存以下8個(gè)單詞：becausebeforebegbeggarbelongbelowdaydeadTrie的特點(diǎn) 根節(jié)點(diǎn)不包含字母，除根節(jié)點(diǎn)外每一個(gè)節(jié)根節(jié)點(diǎn)不包含字母，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都僅包含一個(gè)英文字母點(diǎn)都僅包含一個(gè)英文字母 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字母從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字母依次

2、連起來(lái)所構(gòu)成的字母序列，稱為該節(jié)依次連起來(lái)所構(gòu)成的字母序列，稱為該節(jié)點(diǎn)對(duì)應(yīng)的單詞。點(diǎn)對(duì)應(yīng)的單詞。 每個(gè)節(jié)點(diǎn)的所有兒子包含的字母都不相同。每個(gè)節(jié)點(diǎn)的所有兒子包含的字母都不相同。 插入和刪除的時(shí)間均為插入和刪除的時(shí)間均為O（L） L為字符串的長(zhǎng)度為字符串的長(zhǎng)度字符串的后綴 定義：給定一長(zhǎng)度為定義：給定一長(zhǎng)度為n的字符串的字符串S=S1S2.Si.Sn，和整數(shù)，和整數(shù)i，1 = i nextindex=NULL) p-nextindex=new node(); 7 p=p-nextindex; 8 i+; 9 10 p-count+; /在單詞的最后一個(gè)節(jié)點(diǎn)在單詞的最后一個(gè)節(jié)點(diǎn)count+1，代表一

3、個(gè)單詞，代表一個(gè)單詞11 構(gòu)造失敗指針 構(gòu)造失敗指針的過(guò)程概括起來(lái)就一句話：設(shè)這個(gè)構(gòu)造失敗指針的過(guò)程概括起來(lái)就一句話：設(shè)這個(gè)節(jié)點(diǎn)上的字母為節(jié)點(diǎn)上的字母為C，沿著他父親的失敗指針走，沿著他父親的失敗指針走，直到走到一個(gè)節(jié)點(diǎn)，他的兒子中也有字母為直到走到一個(gè)節(jié)點(diǎn)，他的兒子中也有字母為C的的節(jié)點(diǎn)。然后把當(dāng)前節(jié)點(diǎn)的失敗指針指向那個(gè)字母節(jié)點(diǎn)。然后把當(dāng)前節(jié)點(diǎn)的失敗指針指向那個(gè)字母也為也為C的兒子。如果一直走到了的兒子。如果一直走到了root都沒(méi)找到，都沒(méi)找到，那就把失敗指針指向那就把失敗指針指向root。 具體操作起來(lái)只需要：先把具體操作起來(lái)只需要：先把root加入隊(duì)列加入隊(duì)列(root的的失敗指針指向自

4、己或者失敗指針指向自己或者NULL)，這以后我們每處，這以后我們每處理一個(gè)點(diǎn)，就把它的所有兒子加入隊(duì)列，隊(duì)列為理一個(gè)點(diǎn)，就把它的所有兒子加入隊(duì)列，隊(duì)列為空?？?。1 void build_ac_automation(node *root) 2 int i; 3 root-fail=NULL; /root的失敗指針指向自己或者的失敗指針指向自己或者NULL 4 qhead+=root; /把把root加入隊(duì)列加入隊(duì)列 5 while(head!=tail) 6 node *temp=qtail+; 7 node *p=NULL; 8 for(i=0;inexti!=NULL) 10 if(temp

5、=root) temp-nexti-fail=root; 11 else 12 p=temp-fail; /p指向指向h節(jié)點(diǎn)所指的節(jié)點(diǎn)，也就是節(jié)點(diǎn)所指的節(jié)點(diǎn)，也就是root13 while(p!=NULL) 14 if(p-nexti!=NULL) 15 temp-nexti-fail=p-nexti; 16 break; 17 18 p=p-fail; 19 20 if(p=NULL) temp-nexti-fail=root; 21 22 qhead+=temp-nexti; 23 24 25 26 構(gòu)造失敗指針例圖首先首先root的的fail指針指向指針指向NULL，然后，然后root入

6、隊(duì)，進(jìn)入循環(huán)。第入隊(duì)，進(jìn)入循環(huán)。第1次次循環(huán)的時(shí)候，我們需要處理循環(huán)的時(shí)候，我們需要處理2個(gè)節(jié)點(diǎn)：個(gè)節(jié)點(diǎn)：root-nexth-a(節(jié)點(diǎn)節(jié)點(diǎn)h) 和和 root-nexts-a(節(jié)點(diǎn)節(jié)點(diǎn)s)。把這。把這2個(gè)節(jié)點(diǎn)的失敗指針指向個(gè)節(jié)點(diǎn)的失敗指針指向root，并且先后進(jìn)入隊(duì)列，失敗指針的指向?qū)?yīng)上圖中的，并且先后進(jìn)入隊(duì)列，失敗指針的指向?qū)?yīng)上圖中的(1)，(2)兩條兩條虛線；虛線；第第2次進(jìn)入循環(huán)后，從隊(duì)列中先彈出次進(jìn)入循環(huán)后，從隊(duì)列中先彈出h，接下來(lái)，接下來(lái)p指向指向h節(jié)點(diǎn)的節(jié)點(diǎn)的fail指針指向的節(jié)點(diǎn)，也就是指針指向的節(jié)點(diǎn)，也就是root；進(jìn)入第；進(jìn)入第13行的循環(huán)后，行的循環(huán)后，p=p-fai

7、l也就是也就是p=NULL，這時(shí)退出循環(huán)，并把節(jié)點(diǎn)，這時(shí)退出循環(huán)，并把節(jié)點(diǎn)e的的fail指針指向指針指向root，對(duì)應(yīng)上圖中的，對(duì)應(yīng)上圖中的(3)，然后節(jié)點(diǎn)，然后節(jié)點(diǎn)e進(jìn)入隊(duì)列；進(jìn)入隊(duì)列；第第3次循環(huán)時(shí)，彈出的第一個(gè)節(jié)點(diǎn)次循環(huán)時(shí)，彈出的第一個(gè)節(jié)點(diǎn)a的操作與上一步操作的節(jié)點(diǎn)的操作與上一步操作的節(jié)點(diǎn)e相相同，把同，把a(bǔ)的的fail指針指向指針指向root，對(duì)應(yīng)上圖中的，對(duì)應(yīng)上圖中的(4)，并入隊(duì)；，并入隊(duì)；第第4次進(jìn)入循環(huán)時(shí)，彈出節(jié)點(diǎn)次進(jìn)入循環(huán)時(shí)，彈出節(jié)點(diǎn)h(圖中左邊那個(gè)圖中左邊那個(gè))，這時(shí)操作略有不，這時(shí)操作略有不同。在程序運(yùn)行到同。在程序運(yùn)行到14行時(shí)，由于行時(shí)，由于p-nexti!=NULL

8、(root有有h這個(gè)這個(gè)兒子節(jié)點(diǎn)，圖中右邊那個(gè)兒子節(jié)點(diǎn)，圖中右邊那個(gè))，這樣便把左邊那個(gè)，這樣便把左邊那個(gè)h節(jié)點(diǎn)的失敗指針節(jié)點(diǎn)的失敗指針指向右邊那個(gè)指向右邊那個(gè)root的兒子節(jié)點(diǎn)的兒子節(jié)點(diǎn)h，對(duì)應(yīng)上圖中的，對(duì)應(yīng)上圖中的(5)，然后，然后h入隊(duì)。入隊(duì)。以此類推：在循環(huán)結(jié)束后，所有的失敗指針就是上圖中的這種形以此類推：在循環(huán)結(jié)束后，所有的失敗指針就是上圖中的這種形式。式。匹配單詞 最后，我們便可以在最后，我們便可以在AC自動(dòng)機(jī)上查找模式串中出自動(dòng)機(jī)上查找模式串中出現(xiàn)過(guò)哪些單詞了。現(xiàn)過(guò)哪些單詞了。 匹配過(guò)程分兩種情況：匹配過(guò)程分兩種情況：(1)當(dāng)前字符匹配，表示從當(dāng)前節(jié)點(diǎn)沿著樹(shù)邊有一條當(dāng)前字符匹配，

9、表示從當(dāng)前節(jié)點(diǎn)沿著樹(shù)邊有一條路徑可以到達(dá)目標(biāo)字符，此時(shí)只需沿該路徑走向路徑可以到達(dá)目標(biāo)字符，此時(shí)只需沿該路徑走向下一個(gè)節(jié)點(diǎn)繼續(xù)匹配即可，目標(biāo)字符串指針移向下一個(gè)節(jié)點(diǎn)繼續(xù)匹配即可，目標(biāo)字符串指針移向下個(gè)字符繼續(xù)匹配；下個(gè)字符繼續(xù)匹配；(2)當(dāng)前字符不匹配，則去當(dāng)前節(jié)點(diǎn)失敗指針?biāo)赶虍?dāng)前字符不匹配，則去當(dāng)前節(jié)點(diǎn)失敗指針?biāo)赶虻淖址^續(xù)匹配，匹配過(guò)程隨著指針指向的字符繼續(xù)匹配，匹配過(guò)程隨著指針指向root結(jié)結(jié)束。重復(fù)這束。重復(fù)這2個(gè)過(guò)程中的任意一個(gè)，直到模式串走個(gè)過(guò)程中的任意一個(gè)，直到模式串走到結(jié)尾為止。到結(jié)尾為止。 1 int query(node *root) 2 int i=0,cnt=0,i

10、ndex,len=strlen(str); 3 node *p=root; 4 while(stri) 5 index=stri-a; /index=026 6 while(p-nextindex=NULL & p!=root) p=p-fail; /p指向指向p的失敗指針?biāo)赶虻墓?jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn) 7 p=p-nextindex; /p指向指向index節(jié)點(diǎn)節(jié)點(diǎn) 8 p=(p=NULL)?root:p; 9 node *temp=p; 10 while(temp!=root & temp-count!=-1) 11 cnt+=temp-count; /節(jié)點(diǎn)信息為節(jié)點(diǎn)信息為1時(shí)，時(shí)，c

11、nt+1，12 temp-count=-1; /將將count信息置為信息置為-1，表示已經(jīng)出現(xiàn)過(guò)了，表示已經(jīng)出現(xiàn)過(guò)了13 temp=temp-fail; /temp指向指向e的失敗指針說(shuō)指向的節(jié)點(diǎn)繼的失敗指針說(shuō)指向的節(jié)點(diǎn)繼續(xù)查找續(xù)查找14 15 i+; 16 17 return cnt; 18 匹配示例 模式串為模式串為yasherhs。 對(duì)于對(duì)于i=0,1。Trie中沒(méi)有對(duì)應(yīng)的路徑，故不做任何操作；中沒(méi)有對(duì)應(yīng)的路徑，故不做任何操作；i=2,3,4時(shí)，指針時(shí)，指針p走到左下節(jié)點(diǎn)走到左下節(jié)點(diǎn)e。因?yàn)楣?jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)e的的count信信息為息為1，所以，所以cnt+1，并且將節(jié)點(diǎn)，并且將節(jié)點(diǎn)e的的count值設(shè)置為值設(shè)置為-1，表示改單詞已經(jīng)出現(xiàn)過(guò)了，防止重復(fù)計(jì)數(shù)，最后表示改單詞已經(jīng)出現(xiàn)過(guò)了，防止重復(fù)計(jì)數(shù)，最后temp指指向向e節(jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn)繼續(xù)查找，以此類推，節(jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn)繼續(xù)查找，以此類推，最后最后temp指向指向root，退出，退出while循環(huán)，這個(gè)過(guò)程中循環(huán)，這個(gè)過(guò)程中count增加了增加了2。表示找到了。表示找到了2個(gè)單詞個(gè)單詞she和和he。當(dāng)。當(dāng)i=5時(shí)，