國家集訓(xùn)隊2006論文集 王赟

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

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

2、效。左：圖1，一棵含有五個單詞的trie樹。紅色表示單詞終止的位置?！　∮遥簣D2，由圖1的trie樹改造成的trie圖。紅色表示危險結(jié)點，白色表示真安全結(jié)點，藍色表示新加的邊。為簡單起見，危險結(jié)點以下的結(jié)點及與之關(guān)聯(lián)的邊沒有畫出。一、Trie圖的構(gòu)建我們通過一個例題來探究trie圖的構(gòu)建方法?！纠?】不良單詞探測器【題目描述】給出一個詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞?！据斎搿康谝恍袨橐粋€整數(shù)n，表示不良單詞的個數(shù)。接

3、下來n行是詞典。下面一行為一個整數(shù)m，表示文本的行數(shù)。接下來m行是文本?！据敵觥咳绻谋景涣紗卧~，輸出一行“Yes”，否則輸出一行“No”?！緲永斎搿?rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍。【分析】2006年全國信息學(xué)冬令營講座判斷文本是否包含不良單詞可以一行一行地判斷。而判斷長為L的一行文本s是否含有不良單詞可以這樣進行：讓i從1變化到L，依次判斷s的前i個字符構(gòu)成的字符串是否以不良單詞結(jié)尾。然而，我們希望在判斷s的前k個字符時，能夠利用前k-1個

4、字符的結(jié)果，即這兩個狀態(tài)間可以方便地進行轉(zhuǎn)移。注意到trie樹中的邊正如一個個“方向標”，因此我們有了一個美好的設(shè)想：從根結(jié)點出發(fā)，沿著標有s[1]的邊走一步，再沿標有s[2]的邊走一步，一直這樣走下去！現(xiàn)在有了一個問題：如果從當前走到的結(jié)點出發(fā)，沒有需要走的邊，該怎么辦？只要“創(chuàng)造”一條這樣的邊即可。那么這條邊應(yīng)該指向哪個結(jié)點呢？如果同樣“創(chuàng)造”一個結(jié)點，那是毫無意義的。解決這個問題，要從我們“沿邊走”的動機談起。我們之所以“沿邊走”，是因為我們把結(jié)點看成了狀態(tài)，把邊看成了狀態(tài)間轉(zhuǎn)移的途徑。要確定新加的邊應(yīng)連到哪個結(jié)點，就需要找我們想走到但去不存在的那個結(jié)點與已有

5、的哪個結(jié)點是等價的。那么“等價”的標準是什么呢？我們先來解決另一個問題：定義trie樹中從根結(jié)點到某個結(jié)點的路徑上的邊上的字符連起來形成的字符串為這個結(jié)點的路徑字符串。如果一個結(jié)點的路徑字符串以不良單詞結(jié)尾，那么稱這個結(jié)點為危險結(jié)點，否則稱之為安全結(jié)點。那么如何判斷某個結(jié)點是否危險呢？顯然根結(jié)點是安全結(jié)點。對于一個非根結(jié)點，它是危險結(jié)點的充要條件是：它的路徑字符串本身就是一個不良單詞，或者它的路徑字符串的后綴（一個字符串去掉第一個字符后剩下的部分叫做它的后綴）對應(yīng)的結(jié)點（一個字符串對應(yīng)的結(jié)點是指在trie圖中從根出發(fā)，依次沿該字符串的每個字符走一步所達到的結(jié)點）是危

6、險結(jié)點。如果稱一個結(jié)點的路徑字符串的后綴對應(yīng)的結(jié)點為它的后綴結(jié)點，那么如何求任一結(jié)點的后綴結(jié)點呢？根結(jié)點的后綴結(jié)點是它本身。處于trie樹第二層的結(jié)點的后綴結(jié)點也是根結(jié)點。對于再往下的某個結(jié)點，設(shè)它的路徑字符串的最后一個字符為c，那么這個結(jié)點的后綴為從它在trie樹中父結(jié)點的后綴結(jié)點出發(fā)，沿標有c的邊走一步后到達的結(jié)點。（下文中稱從x結(jié)點出發(fā)，沿標有字符c的邊走一步到達的結(jié)點為x的c孩子）那么，如果它的父結(jié)點的后綴結(jié)點w沒有c孩子怎么辦呢？到此，我們看到兩個問題已經(jīng)合而為一了。我們假設(shè)w有這樣一個c孩子（記作x），并且從x出發(fā)又繁衍出無數(shù)的子子孫孫。我們來判斷以x為

7、根的子樹中的結(jié)點的危險性。顯然x本身的路徑字符串不是不良單詞，且它的子孫的路徑字符串也不是不良單詞。因此以x為根的子樹中任一結(jié)點y的危險性與y的后綴結(jié)點的危險性相同（回憶一下一個非根結(jié)點是危險結(jié)點的充要條件）。這也就是說，以x為根的子樹與以x的后綴結(jié)點為根的子樹是一模一樣的。因此，我們把需要新建的從w指向x的邊直接指向x的后綴結(jié)點，即w結(jié)點的后綴結(jié)點的c孩子即可。簡言之，由于x本身的路徑字符串既不是不良單詞，又不是某個不良單詞開頭的一部分，所以它的首字母便沒有用了！在這種情況下，x結(jié)點就等價于它的后綴結(jié)點。由此我們可以把trie樹改造成一個有向圖：按層次遍歷tr