算法合集之trie圖的構(gòu)建、活用與改進(jìn)(存儲(chǔ)版)
【正文】 只有真安全結(jié)點(diǎn)?！据敵觯ǎ咳舸嬖跓o限長的安全代碼，輸出一行“TAK”，否則輸出一行“NIE”?！据敵觯?biāo)準(zhǔn)輸出）】一個(gè)整數(shù)，表示長度為m且不含不良單詞的字符串的數(shù)目。我們看到，trie圖的安全圖上還是大有文章可做的?！据斎耄?biāo)準(zhǔn)輸入）】第一行為一個(gè)整數(shù)n(1=n=10000)，表示不良單詞的個(gè)數(shù)?！緲永斎搿?robProblem1Internet Problem Solving Contest【樣例輸出】1 10【注意】樣例中“第一次出現(xiàn)”的不良單詞是Problem而不是rob，雖然rob比Problem先結(jié)束。Trie樹中的邊自然是要存儲(chǔ)的（用左孩子右兄弟表示法），但新建的邊則不必存儲(chǔ)。我們分別討論增加的這點(diǎn)時(shí)間對(duì)建圖過程和文本檢查過程所需時(shí)間的影響：178。因?yàn)楣鈽?biāo)如果往下走，它只能走1步，所以若把光標(biāo)經(jīng)過的位置的深度也排成一個(gè)數(shù)列，這個(gè)數(shù)列與上一段提到的數(shù)列具有相同的性質(zhì)：增長是緩慢的。如果字符集較大甚至無限（漢字的多模式匹配系統(tǒng)的字符集幾乎可以認(rèn)為是無限的），就必須使用改進(jìn)的trie圖。對(duì)于什么樣的題目需要用改進(jìn)的trie圖，在此作一下總結(jié)：178。178。其實(shí)，算法的時(shí)間復(fù)雜度為O(L1+L2)，數(shù)量級(jí)并沒有受到影響，只是增加了一點(diǎn)常數(shù)系數(shù)。我們看到，在本題中，算法的瓶頸在于從每個(gè)結(jié)點(diǎn)出發(fā)的邊數(shù)?！据敵觯?biāo)準(zhǔn)輸出）】若文本中有不良單詞，輸出一行兩個(gè)整數(shù)，表示不良單詞第一次出現(xiàn)的行和列，用一個(gè)空格隔開。再給出一段文本，文本的每一行可能包含除chr(0),chr(10),chr(13)外的任何字符。for 安全圖中每個(gè)結(jié)點(diǎn)x doinc(ans,count[m,x])。第二行為n個(gè)字符，表示字符集。下面n行，每行一段病毒特征代碼。但如果僅僅用trie圖來做多模式匹配，那就太大材小用了。通過《字謎》一題我們學(xué)會(huì)了如何在trie圖中記下更多的信息。我們定義危險(xiǎn)結(jié)點(diǎn)x的危險(xiǎn)源：若x的路徑字符串本身就是不良單詞，那么它的危險(xiǎn)源就是該單詞；否則x的危險(xiǎn)源就是它后綴結(jié)點(diǎn)的危險(xiǎn)源。下面L行，每行C個(gè)大寫字母，表示矩陣。二、Trie圖的活用在上面的例題中，我們在trie圖中記錄了每個(gè)結(jié)點(diǎn)的危險(xiǎn)性、后綴結(jié)點(diǎn)，并通過按層次遍歷得到了圖中結(jié)點(diǎn)的一個(gè)BFS序。我們美好的設(shè)想終于變成了現(xiàn)實(shí)。因此，我們把需要新建的從w指向x的邊直接指向x的后綴結(jié)點(diǎn)，即w結(jié)點(diǎn)的后綴結(jié)點(diǎn)的c孩子即可。處于trie樹第二層的結(jié)點(diǎn)的后綴結(jié)點(diǎn)也是根結(jié)點(diǎn)。解決這個(gè)問題，要從我們“沿邊走”的動(dòng)機(jī)談起。接下來m行是文本。【例1】不良單詞探測器【題目描述】給出一個(gè)詞典，其中的單詞為不良單詞。利用trie樹可以對(duì)詞典中的單詞進(jìn)行一些適合用樹這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的操作，如求兩個(gè)單詞的公共前綴長度（在樹中表現(xiàn)為求兩個(gè)單詞對(duì)應(yīng)結(jié)點(diǎn)的最近公共祖先）。圖1就是一棵trie樹，其中含有a,abc,bac,bbc,ca五個(gè)單詞。一、Trie圖的構(gòu)建我們通過一個(gè)例題來探究trie圖的構(gòu)建方法。下面一行為一個(gè)整數(shù)m，表示文本的行數(shù)。那么這條邊應(yīng)該指向哪個(gè)結(jié)點(diǎn)呢？如果同樣“創(chuàng)造”一個(gè)結(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)是它本身。這也就是說，以x為根的子樹與以x的后綴結(jié)點(diǎn)為根的子樹是一模一樣的。圖2就是
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1