算法合集之多串匹配算法及其啟示(編輯修改稿)
2024-11-14 18:36 本頁面
【文章內(nèi)容簡介】 ，記錄每一個結(jié)點到達任意一個Okay結(jié)點（自身除外）的最短路徑（既可以通過樹中的邊，也可以通過前綴指針） 主算法二（續(xù)） ?舉例 a b b a b a b 1 1 1 1 1 2 2 2 主算法二（續(xù)） ?后綴樹的使用和擴展 (TreeB) ? 由所有模式串倒置后的所有后綴組成。 ?模式串為“ abab”“ba”“bb” ?倒置：“ baba”“ab”“bb” ?作用： ? 在 O(N)的時間內(nèi)，從后向 前地查看一段長度為 N的字 符，檢測它是否為任意一個 模式串的子串 a b b a b ab 主算法二（續(xù)） ? TreeA上的函數(shù) ScanA ? Function ScanA(Left,Right,P)。 ? 如果 Shift參數(shù) 最短的模式串長度 div 2，繼續(xù)讀入字符并且 P繼續(xù)移動 ? 輸出所有遇到的匹配 x x x x xxxx Right Left x x x x P 主算法二（續(xù)） ? TreeB上的函數(shù) ScanB ? Function ScanB(Left,Right)。 ? 在 TreeB中，將 T[Left..Right]從右向左進行掃描，檢查其是否為某個模式串的子串，返回最后掃描到的正文的位置。 ? 定義： 當一個字符串是某個模式串的子串時，稱其為“ 有效的 ”，反之為“ 無效的 ”。 主算法二（續(xù)） ?主過程的基本思想： ? 每次處理一個 Left+1~Right的段落 ? 從 Right向左通過 ScanB檢索，最后到達位置 pos。 ? 從 pos到 Right進行 ScanA檢索。 ? 下一個過程的 Left為 ScanA檢索到的正文位置， Right為 Left + 當前 TreeA上的結(jié)點的Shift參數(shù) 主算法二（續(xù)） ?舉例 ? 模式串為 “ abcd”和 “ bcde” ? Tree
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1