算法合集之《trie圖的構(gòu)建、活用與改進(jìn)》-全文預(yù)覽
【正文】 不良單詞的字符串的數(shù)目?！据敵觯ǎ咳舸嬖跓o限長(zhǎng)的安全代碼，輸出一行“TAK”，否則輸出一行“NIE”。給定病毒特征庫(kù)，判斷是否存在無限長(zhǎng)的安全代碼。從例1可以看到，危險(xiǎn)結(jié)點(diǎn)在圖中往往是一些障礙，在許多用到trie圖的問題中，有用的結(jié)點(diǎn)只有真安全結(jié)點(diǎn)。這樣處理之后，有單詞對(duì)應(yīng)的結(jié)點(diǎn)的訪問次數(shù)就代表這個(gè)單詞出現(xiàn)的次數(shù)了。在做多模式匹配時(shí)，有時(shí)僅僅找到不良單詞是不夠的，還要統(tǒng)計(jì)出每個(gè)單詞出現(xiàn)的次數(shù)?！咀ⅰ勘绢}的字符集雖然只有26個(gè)字母，但trie圖中結(jié)點(diǎn)的數(shù)目可能達(dá)到1,000,000，內(nèi)存復(fù)雜度太高。那么，是不是每走到一個(gè)危險(xiǎn)結(jié)點(diǎn)，便記下危險(xiǎn)源的位置及朝向就可以了呢？不是的。對(duì)每個(gè)方向的每一串字母進(jìn)行一次多模式匹配，就可以找到所有的單詞了?！据敵觯?biāo)準(zhǔn)輸出）】對(duì)每組數(shù)據(jù)，輸出W行，每行為兩個(gè)整數(shù)和一個(gè)字母，之間用一個(gè)空格隔開。下面有T組數(shù)據(jù)?！纠?】字謎（題目來源：SPOJ WPUZZLES）【題目描述】給定一個(gè)L行C列的、由大寫字母構(gòu)成的矩陣，以及W個(gè)單詞。而在本題中，一旦到達(dá)一個(gè)危險(xiǎn)結(jié)點(diǎn)，程序就會(huì)停止，因此假安全結(jié)點(diǎn)是沒有用的，也就是說，在本題trie圖的構(gòu)建過程中，若發(fā)現(xiàn)一個(gè)危險(xiǎn)結(jié)點(diǎn)，那么它及它的子孫的屬性都不必計(jì)算了。若走到一個(gè)危險(xiǎn)結(jié)點(diǎn)，則發(fā)現(xiàn)了一個(gè)不良單詞；若一直沒走到危險(xiǎn)結(jié)點(diǎn)，則文本不含不良單詞。這樣由trie樹改造成的有向圖就叫做trie圖。由此我們可以把trie樹改造成一個(gè)有向圖：按層次遍歷trie樹，求出每個(gè)結(jié)點(diǎn)的危險(xiǎn)性和后綴結(jié)點(diǎn)，并補(bǔ)齊由它出發(fā)的邊。因此以x為根的子樹中任一結(jié)點(diǎn)y的危險(xiǎn)性與y的后綴結(jié)點(diǎn)的危險(xiǎn)性相同（回憶一下一個(gè)非根結(jié)點(diǎn)是危險(xiǎn)結(jié)點(diǎn)的充要條件）。（下文中稱從x結(jié)點(diǎn)出發(fā)，沿標(biāo)有字符c的邊走一步到達(dá)的結(jié)點(diǎn)為x的c孩子）那么，如果它的父結(jié)點(diǎn)的后綴結(jié)點(diǎn)w沒有c孩子怎么辦呢？到此，我們看到兩個(gè)問題已經(jīng)合而為一了。對(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é)點(diǎn)）是危險(xiǎn)結(jié)點(diǎn)。要確定新加的邊應(yīng)連到哪個(gè)結(jié)點(diǎn)，就需要找我們想走到但去不存在的那個(gè)結(jié)點(diǎn)與已有的哪個(gè)結(jié)點(diǎn)是等價(jià)的。注意到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)造”一條這樣的邊即可。【樣例輸入】1rob1internetproblemsolvingcontest【樣例輸出】Yes【備注】因本題只是用來討論trie圖的構(gòu)建方法，故未給出數(shù)據(jù)范圍。接下來n行是詞典。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。為簡(jiǎn)單起見，危險(xiǎn)結(jié)點(diǎn)以下的結(jié)點(diǎn)及與之關(guān)聯(lián)的邊沒有畫出。左：圖1，一棵含有五個(gè)單詞的trie樹。詞典中的每一個(gè)單詞在trie樹中表現(xiàn)為一條從根結(jié)點(diǎn)出發(fā)的路徑，路徑中邊上的字母連起來就形成對(duì)應(yīng)的單詞。它是詞典的一種存儲(chǔ)方式。其實(shí)，如果把trie樹加以改造，多連一些邊，形成的trie圖在解決多模式串匹配問題上會(huì)發(fā)揮奇效。紅色表示危險(xiǎn)結(jié)點(diǎn)，白色表示真安全結(jié)點(diǎn)，藍(lán)色表示新加的邊。單詞均為小寫字母?！据斎搿康谝恍袨橐粋€(gè)整
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1