算法合集之trie圖的構建、活用與改進-文庫吧資料
2024-10-22 20:29本頁面
【正文】 1=m=50)且不含不良單詞的字符串的數目 ?！?無限步 ” 又是什么意思呢 ？ 就是說安全圖中有環(huán) 。 【 輸出 （ 文件 ） 】 若存在無限長的安全代碼 ， 輸出一行 “ TAK” ， 否則輸出一行 “ NIE” 。 下面 n行 ， 每行一段病毒特征代碼 。 給定病毒特征庫 ， 判斷是否存在無限長的安全代碼 。 Trie圖的活用（例 3） 【 例 3】 病毒 （ 題目來源： POI 7） 【 題目描述 】 已知某些特定的 01串是病毒的特征代碼 。 ? 從例 1可以看到 ， 危險結點在圖中往往是一些障礙 ， 在許多用到 trie圖的問題中 ， 有用的結點只有真安全結點 。 但如果僅僅用 trie圖來做多模式匹配 ， 那就太大材小用了 。這樣處理之后，有單詞對應的結點的訪問次數就代表這個單詞出現的次數了。但這時有單詞對應的結點的訪問次數并不就是這個單詞出現的次數，比如在圖 2中，單詞 a出現時光標完全可能在結點 ba上。 ? 在做多模式匹配時，有時僅僅找到不良單詞是不夠的，還要統(tǒng)計出每個單詞出現的次數。 Trie圖的活用（ BFS序的應用） ? 通過 《 字謎 》 一題我們學會了如何在 trie圖中記下更多的信息。 Trie圖的活用（例 2的遺留問題） ? 例 2的字符集雖然只有 26個字母，但 trie圖中結點的數目可能達到 1,000,000，內存復雜度太高。但同時我們就把單詞 ARM漏掉了。 Trie圖的活用（例 2分析） MAIGO QKRPT AREMO WERTY ? 那么，是不是每走到一個危險結點，便記下危險源的位置及朝向就可以了呢？不是的。我們定義危險結點 x的 危險源 ： ? 若 x的路徑字符串本身就是不良單詞，那么它的危險源就是該單詞； ? 否則 x的危險源就是它后綴結點的危險源。對每個方向的每一串字母進行一次多模式匹配，就可以找到所有的單詞了。 字母 A B C D E F G H 朝向 上 右上 右 右下 下 左下 左 左上 Trie圖的活用（例 2） 【 樣例輸入 】 1 4 5 4 MAIGO QKRPT AREMO WERTY AKI MAIGO ARM ARMY 【 樣例輸出 】 2 0 B 0 0 C 0 1 D 0 1 D Trie圖的活用（例 2分析） ? 本題中多模式匹配的模型是顯而易見的。 Trie圖的活用（例 2） 【 輸出 （ 標準輸出 ） 】 對每組數據 ， 輸出 W行 ， 每行為兩個整數和一個字母 ， 之間用一個空格隔開 。 ? 下面 L行 ， 每行 C個大寫字母 ， 表示矩陣 。 下面有 T組數據 。 編程找出每個單詞的首字母在矩陣中的位置 ， 以及單詞的朝向 。 Trie圖的活用（例 2） 【 例 2】 字謎 （ 題目來源： SPOJ WPUZZLES） 【 題目描述 】 給定一個 L行 C列的 、 由大寫字母構成的矩陣 ，以及 W個單詞 。 Trie圖的活用 ? 在上面的例題中，我們在 trie圖中記錄了每個結點的危險性、后綴結點，并通過按層次遍歷得到了圖中結點的一個 BFS序。而在本題中，一旦到達一個危險結點，程序就會停止，因此假安全結點是沒有用的，也就是說，在本題trie圖的構建過程中，若發(fā)現一個危險結點，那么它及它的子孫的屬性都不必計算了。把安全結點分為兩類：如果在 trie樹中由根結點到某個安全結點的路徑上沒有危險結點，那么稱這個安全結點為 真安全結點 ，否則稱之為 假安全結點 。若走到一個危險結點，則發(fā)現了一個不良單詞；若一直沒走到危險結點，則文本不含不良單詞。我們美好的設想終于變成了現實。 Trie圖的構建（構建流程演示） 結點 后綴 a孩子 b孩子 c孩子 0 0 1 4 9 1 0 1 2 9 2 4 5 7 3 3 9 10 4 9 4 0 5 7 9 5 1 1 2 6 6 9 10 4 9
教學課件相關推薦
鄂ICP備17016276號-1