國(guó)家集訓(xùn)隊(duì)2006論文集 王赟

《國(guó)家集訓(xùn)隊(duì)2006論文集 王赟》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、2006年全國(guó)信息學(xué)冬令營(yíng)講座Trie圖的構(gòu)建、活用與改進(jìn)Maigo2006.1.14我們知道trie樹(shù)（也叫字母樹(shù)）這種數(shù)據(jù)結(jié)構(gòu)。它是詞典的一種存儲(chǔ)方式。詞典中的每一個(gè)單詞在trie樹(shù)中表現(xiàn)為一條從根結(jié)點(diǎn)出發(fā)的路徑，路徑中邊上的字母連起來(lái)就形成對(duì)應(yīng)的單詞。圖1就是一棵trie樹(shù)，其中含有a,abc,bac,bbc,ca五個(gè)單詞。利用trie樹(shù)可以對(duì)詞典中的單詞進(jìn)行一些適合用樹(shù)這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的操作，如求兩個(gè)單詞的公共前綴長(zhǎng)度（在樹(shù)中表現(xiàn)為求兩個(gè)單詞對(duì)應(yīng)結(jié)點(diǎn)的最近公共祖先）。其實(shí)，如果把trie樹(shù)加以改造，多連一些邊，形成的trie圖在

2、解決多模式串匹配問(wèn)題上會(huì)發(fā)揮奇效。左：圖1，一棵含有五個(gè)單詞的trie樹(shù)。紅色表示單詞終止的位置?！　∮遥簣D2，由圖1的trie樹(shù)改造成的trie圖。紅色表示危險(xiǎn)結(jié)點(diǎn)，白色表示真安全結(jié)點(diǎn)，藍(lán)色表示新加的邊。為簡(jiǎn)單起見(jiàn)，危險(xiǎn)結(jié)點(diǎn)以下的結(jié)點(diǎn)及與之關(guān)聯(lián)的邊沒(méi)有畫出。一、Trie圖的構(gòu)建我們通過(guò)一個(gè)例題來(lái)探究trie圖的構(gòu)建方法。【例1】不良單詞探測(cè)器【題目描述】給出一個(gè)詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有

3、不良單詞?！据斎搿康谝恍袨橐粋€(gè)整數(shù)n，表示不良單詞的個(gè)數(shù)。接下來(lái)n行是詞典。下面一行為一個(gè)整數(shù)m，表示文本的行數(shù)。接下來(lái)m行是文本。【輸出】如果文本包含不良單詞，輸出一行“Yes”，否則輸出一行“No”?！緲永斎搿?rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來(lái)討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍。【分析】2006年全國(guó)信息學(xué)冬令營(yíng)講座判斷文本是否包含不良單詞可以一行一行地判斷。而判斷長(zhǎng)為L(zhǎng)的一行文本s是否含有不良單詞可以這樣進(jìn)行：讓i從1變化到L，依次判斷s的前i個(gè)字

4、符構(gòu)成的字符串是否以不良單詞結(jié)尾。然而，我們希望在判斷s的前k個(gè)字符時(shí)，能夠利用前k-1個(gè)字符的結(jié)果，即這兩個(gè)狀態(tài)間可以方便地進(jìn)行轉(zhuǎn)移。注意到trie樹(shù)中的邊正如一個(gè)個(gè)“方向標(biāo)”，因此我們有了一個(gè)美好的設(shè)想：從根結(jié)點(diǎn)出發(fā)，沿著標(biāo)有s[1]的邊走一步，再沿標(biāo)有s[2]的邊走一步，一直這樣走下去！現(xiàn)在有了一個(gè)問(wèn)題：如果從當(dāng)前走到的結(jié)點(diǎn)出發(fā)，沒(méi)有需要走的邊，該怎么辦？只要“創(chuàng)造”一條這樣的邊即可。那么這條邊應(yīng)該指向哪個(gè)結(jié)點(diǎn)呢？如果同樣“創(chuàng)造”一個(gè)結(jié)點(diǎn)，那是毫無(wú)意義的。解決這個(gè)問(wèn)題，要從我們“沿邊走”的動(dòng)機(jī)談起。我們之所以“沿邊走”，是因?yàn)槲覀?/p>

5、把結(jié)點(diǎn)看成了狀態(tài)，把邊看成了狀態(tài)間轉(zhuǎn)移的途徑。要確定新加的邊應(yīng)連到哪個(gè)結(jié)點(diǎn)，就需要找我們想走到但去不存在的那個(gè)結(jié)點(diǎn)與已有的哪個(gè)結(jié)點(diǎn)是等價(jià)的。那么“等價(jià)”的標(biāo)準(zhǔn)是什么呢？我們先來(lái)解決另一個(gè)問(wèn)題：定義trie樹(shù)中從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的邊上的字符連起來(lái)形成的字符串為這個(gè)結(jié)點(diǎn)的路徑字符串。如果一個(gè)結(jié)點(diǎn)的路徑字符串以不良單詞結(jié)尾，那么稱這個(gè)結(jié)點(diǎn)為危險(xiǎn)結(jié)點(diǎn)，否則稱之為安全結(jié)點(diǎn)。那么如何判斷某個(gè)結(jié)點(diǎn)是否危險(xiǎn)呢？顯然根結(jié)點(diǎn)是安全結(jié)點(diǎn)。對(duì)于一個(gè)非根結(jié)點(diǎn)，它是危險(xiǎn)結(jié)點(diǎn)的充要條件是：它的路徑字符串本身就是一個(gè)不良單詞，或者它的路徑字符串的后綴（一個(gè)字符

6、串去掉第一個(gè)字符后剩下的部分叫做它的后綴）對(duì)應(yīng)的結(jié)點(diǎn)（一個(gè)字符串對(duì)應(yīng)的結(jié)點(diǎn)是指在trie圖中從根出發(fā)，依次沿該字符串的每個(gè)字符走一步所達(dá)到的結(jié)點(diǎn)）是危險(xiǎn)結(jié)點(diǎn)。如果稱一個(gè)結(jié)點(diǎn)的路徑字符串的后綴對(duì)應(yīng)的結(jié)點(diǎn)為它的后綴結(jié)點(diǎn)，那么如何求任一結(jié)點(diǎn)的后綴結(jié)點(diǎn)呢？根結(jié)點(diǎn)的后綴結(jié)點(diǎn)是它本身。處于trie樹(shù)第二層的結(jié)點(diǎn)的后綴結(jié)點(diǎn)也是根結(jié)點(diǎn)。對(duì)于再往下的某個(gè)結(jié)點(diǎn)，設(shè)它的路徑字符串的最后一個(gè)字符為c，那么這個(gè)結(jié)點(diǎn)的后綴為從它在trie樹(shù)中父結(jié)點(diǎn)的后綴結(jié)點(diǎn)出發(fā)，沿標(biāo)有c的邊走一步后到達(dá)的結(jié)點(diǎn)。（下文中稱從x結(jié)點(diǎn)出發(fā)，沿標(biāo)有字符c的邊走一步到達(dá)的結(jié)點(diǎn)為x的c孩子）

7、那么，如果它的父結(jié)點(diǎn)的后綴結(jié)點(diǎn)w沒(méi)有c孩子怎么辦呢？到此，我們看到兩個(gè)問(wèn)題已經(jīng)合而為一了。我們假設(shè)w有這樣一個(gè)c孩子（記作x），并且從x出發(fā)又繁衍出無(wú)數(shù)的子子孫孫。我們來(lái)判斷以x為根的子樹(shù)中的結(jié)點(diǎn)的危險(xiǎn)性。顯然x本身的路徑字符串不是不良單詞，且它的子孫的路徑字符串也不是不良單詞。因此以x為根的子樹(shù)中任一結(jié)點(diǎn)y的危險(xiǎn)性與y的后綴結(jié)點(diǎn)的危險(xiǎn)性相同（回憶一下一個(gè)非根結(jié)點(diǎn)是危險(xiǎn)結(jié)點(diǎn)的充要條件）。這也就是說(shuō)，以x為根的子樹(shù)與以x的后綴結(jié)點(diǎn)為根的子樹(shù)是一模一樣的。因此，我們把需要新建的從w指向x的邊直接指向x的后綴結(jié)點(diǎn)，即w結(jié)點(diǎn)的后綴結(jié)點(diǎn)的c孩子即

8、可。簡(jiǎn)言之，由于x本身的路徑字符串既不是不良單詞，又不是某個(gè)不良單詞開(kāi)頭的一部分，所以它的首字母便沒(méi)有用了！在這種情況下，x結(jié)點(diǎn)就等價(jià)于它的后綴結(jié)點(diǎn)。由此我們可以把trie樹(shù)改造成一個(gè)有向圖：按層次遍歷tr