國家集訓隊2006論文集 王赟

《國家集訓隊2006論文集 王赟》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

3、下來n行是詞典。下面一行為一個整數m，表示文本的行數。接下來m行是文本。【輸出】如果文本包含不良單詞，輸出一行“Yes”，否則輸出一行“No”?！緲永斎搿?rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來討論trie圖的構建方法，故未給出數據范圍?！痉治觥?006年全國信息學冬令營講座判斷文本是否包含不良單詞可以一行一行地判斷。而判斷長為L的一行文本s是否含有不良單詞可以這樣進行：讓i從1變化到L，依次判斷s的前i個字符構成的字符串是否以不良單詞結尾。然而，我們希望在判斷s的前k個字符時，能夠利用前k-1個

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

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

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

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