算法合集之trie圖的構建、活用與改進(編輯修改稿)
2024-11-12 20:29 本頁面
【文章內容簡介】 大寫字母 ， 表示矩陣 。 ? 下面 W行 ， 每行一個單詞 。 Trie圖的活用（例 2） 【 輸出 （ 標準輸出 ） 】 對每組數(shù)據(jù) ， 輸出 W行 ， 每行為兩個整數(shù)和一個字母 ， 之間用一個空格隔開 。 第 i行的兩個整數(shù)表示第 i個單詞首字母的行號和列號 （ 從上至下依次為第 0至 L1行 ， 從左往右依次為第 0至 C1列 ） ；字母表示單詞的朝向 ， 對應關系如下： 相鄰兩組數(shù)據(jù)的輸出之間用一個空行隔開 。 字母 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圖時，把每個單詞都反過來，如單詞 MAIGO變成 OGIAM。對每個方向的每一串字母進行一次多模式匹配，就可以找到所有的單詞了。 ? 在本題的 trie圖中，僅僅記錄每個結點的危險性是不夠的，還要記下每個結點的危險性是由哪個單詞引起的。我們定義危險結點 x的 危險源 ： ? 若 x的路徑字符串本身就是不良單詞，那么它的危險源就是該單詞； ? 否則 x的危險源就是它后綴結點的危險源。 ? 每個結點的危險源可以在后綴結點的過程中求出。 Trie圖的活用（例 2分析） MAIGO QKRPT AREMO WERTY ? 那么，是不是每走到一個危險結點，便記下危險源的位置及朝向就可以了呢？不是的。比如在樣例中，當我們沿著左上方向掃描 (3,4)(0,1)這個字符串（ YMRA），到達字母 A時，由于該結點的危險源是 YMRA，我們便記下了 ARMY的位置和朝向。但同時我們就把單詞 ARM漏掉了。正確的做法是，當遇到一個危險結點時，記下它的危險源的位置和朝向，同時繼續(xù)檢查危險源對應結點的后綴結點，直到到達一個安全結點為止。 Trie圖的活用（例 2的遺留問題） ? 例 2的字符集雖然只有 26個字母，但 trie圖中結點的數(shù)目可能達到 1,000,000，內存復雜度太高。這個問題留待第三部分（ trie圖的改進） 解決。 Trie圖的活用（ BFS序的應用） ? 通過 《 字謎 》 一題我們學會了如何在 trie圖中記下更多的信息。下面簡述一下對 BFS序的應用。 ? 在做多模式匹配時，有時僅僅找到不良單詞是不夠的，還要統(tǒng)計出每個單詞出現(xiàn)的次數(shù)。進行這項工作時，我們并不需要判斷每個結點的危險性，而只需累加經(jīng)過每個結點的次數(shù)。但這時有單詞對應的結點的訪問次數(shù)并不就是這個單詞出現(xiàn)的次數(shù)，比如在圖 2中，單詞 a出現(xiàn)時光標完全可能在結點 ba上。因此我們自底向上地把每個結點的訪問次數(shù)加到它的后綴結點上。這樣處理之后，有單詞對應的結點的訪問次數(shù)就代表這個單詞出現(xiàn)的次數(shù)了。 Trie圖的活用 ? 上面介紹了 trie圖的一些初步活用 。 但如果僅僅用 trie圖來做多模式匹配 ， 那就太大材小用了 。下面再通過幾個例題來說明 trie圖的更靈活的應用 。 ? 從例 1可以看到 ， 危險結點在圖中往往是一些障礙 ， 在許多用到 trie圖的問題中 ， 有用的結點只有真安全結點 。 我們把 trie圖中的真安全結點以及它們之間的邊構成的子圖叫做 安全圖 。 Trie圖的活用（例 3） 【 例 3】 病毒 （ 題目來源： POI 7） 【 題目描述 】 已知某些特定的 01串是病毒的特征代碼 。 如果一個 01串不含有任何病毒特征代碼 ， 則稱它為一段安全代碼 。 給定病毒特征庫 ， 判斷是否存在無限長的安全代碼 。 【 輸入 （ 文件 ） 】 第一行為一個整數(shù) n， 表示病毒特征
教學課件相關推薦
鄂ICP備17016276號-1