算法合集之trie圖的構(gòu)建、活用與改進(jìn)(已修改)
2025-09-04 15:51 本頁面
【正文】 2006年全國(guó)信息學(xué)冬令營(yíng)講座Trie圖的構(gòu)建、活用與改進(jìn) Maigo 我們知道trie樹（也叫字母樹）這種數(shù)據(jù)結(jié)構(gòu)。它是詞典的一種存儲(chǔ)方式。詞典中的每一個(gè)單詞在trie樹中表現(xiàn)為一條從根結(jié)點(diǎn)出發(fā)的路徑，路徑中邊上的字母連起來就形成對(duì)應(yīng)的單詞。圖1就是一棵trie樹，其中含有a,abc,bac,bbc,ca五個(gè)單詞。利用trie樹可以對(duì)詞典中的單詞進(jìn)行一些適合用樹這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的操作，如求兩個(gè)單詞的公共前綴長(zhǎng)度（在樹中表現(xiàn)為求兩個(gè)單詞對(duì)應(yīng)結(jié)點(diǎn)的最近公共祖先）。其實(shí)，如果把trie樹加以改造，多連一些邊，形成的trie圖在解決多模式串匹配問題上會(huì)發(fā)揮奇效。左：圖1，一棵含有五個(gè)單詞的trie樹。紅色表示單詞終止的位置?！ ∮遥簣D2，由圖1的trie樹改造成的trie圖。紅色表示危險(xiǎn)結(jié)點(diǎn)，白色表示真安全結(jié)點(diǎn)，藍(lán)色表示新加的邊。為簡(jiǎn)單起見，危險(xiǎn)結(jié)點(diǎn)以下的結(jié)點(diǎn)及與之關(guān)聯(lián)的邊沒有畫出。一、Trie圖的構(gòu)建我們通過一個(gè)例題來探究trie圖的構(gòu)建方法。【例1】不良單詞探測(cè)器【題目描述】給出一個(gè)詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞?！据斎搿康谝恍袨橐粋€(gè)整數(shù)n，表示不良單詞的個(gè)數(shù)。接下來n行是詞典。下面一行為一個(gè)整數(shù)m，表示文本的行數(shù)。接下來m行是文本。【輸出】如果文本包含不良單詞，輸出一行“Yes”，否則輸出一行“No”。【樣例輸入】1rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍?！痉治觥颗袛辔谋臼欠癜涣紗卧~可以一行一行地判斷。而判斷長(zhǎng)為L(zhǎng)的一行文本s是否含有不良單詞可以這樣進(jìn)行：讓i從1變化到L，依次判斷s的前i個(gè)字符構(gòu)成的字符串是否以不良單詞結(jié)尾。然而，我們希望在判斷s的前k個(gè)字符時(shí)，能夠利用前k1個(gè)字符的結(jié)果，即這兩個(gè)狀態(tài)間可以方便地進(jìn)行轉(zhuǎn)移。注意到trie樹中的邊正如一個(gè)個(gè)“方向標(biāo)”，因此我們有了一個(gè)美好的設(shè)想：從根結(jié)點(diǎn)出發(fā)，沿著標(biāo)有s[1]的邊走一步，再沿標(biāo)有s[2]的邊走一步，一直這樣走下去！現(xiàn)在有了一個(gè)問題：如果從當(dāng)前走到的結(jié)點(diǎn)出發(fā)，沒有需要走的邊，該怎么辦？只要“創(chuàng)造”一條這樣的邊即可。那么這條邊應(yīng)該指向哪個(gè)結(jié)點(diǎn)呢？如果同樣“創(chuàng)造”一個(gè)結(jié)點(diǎn)，那是毫無意義的。解決這個(gè)問題，要從我們“沿邊走”的動(dòng)機(jī)談起。我們之所以“沿邊走”，是因?yàn)槲覀儼呀Y(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)是什么呢？我們先來解決另一個(gè)問題：定義trie樹中從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的邊上的字符連起來形成的字符串為這個(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è)字符串去掉第一個(gè)字符后剩下的部分叫做它的后綴）對(duì)應(yīng)的結(jié)點(diǎn)（一個(gè)字符串對(duì)應(yīng)的結(jié)點(diǎn)是指在trie圖中從根出發(fā)，依次沿該字符串的每個(gè)字符走一步所達(dá)到的結(jié)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1