信息學競賽冬令營集

多串匹配算法

及其啟示南京市外國語學校朱澤園

問題提出所謂多串匹配，就是給定一些模式串，在一段文章（只出現(xiàn)小寫a到z這26個字母）中，找出第一個出現(xiàn)的任意一個模式串的位置，或者所有模式串出現(xiàn)的所有位置。例子模式串：“abcd”“bcde”正文：abcabcde實際應用含邏輯關(guān)鍵字的搜索引擎DNA序列搜索……廣!因此用有效算法解決該問題能大大提高各行各業(yè)的工作效率！數(shù)據(jù)規(guī)模設(shè)共有m個模式串，長度分別為L1、L2…Lm

正文為一個長度為n的數(shù)組T[1..n]，限定樸素想法從小到大枚舉每一個位置，并且對所有模式串進行檢查。最壞情況下時間復雜度為

對每一個模式串，使用kmp算法進行單串匹配，時間復雜度為我的算法輔助算法1：Knuth-Morris-Pratt模式匹配輔助算法2：單詞前綴樹（自創(chuàng)）主算法1：線性算法輔助算法3：后綴樹主算法2：平均性能更好的算法單詞前綴樹單詞查找樹前綴指針的定義單詞前綴樹之所以不同于單詞樹，是因為它的每一個非根結(jié)點上都有一個前綴指針（PrefixPointer）。設(shè)s為結(jié)點p在樹中對應的字符串s的所有后綴中，找到在單詞樹中出現(xiàn)的，最長的一個，設(shè)為s1。p結(jié)點的前綴指針指向s1對應的結(jié)點。單詞前綴樹（續(xù)）舉例abbabab“bab”不在樹中“ab”在樹中！所以前綴指針指向“ab”單詞前綴樹（續(xù)）前綴指針的生成從定義出發(fā)，窮舉+掃描從kmp算法的前綴數(shù)組中吸取經(jīng)驗，通過父節(jié)點的前綴指針計算b單詞前綴樹（續(xù)）舉例abbabab結(jié)點p結(jié)點q1結(jié)點q2主算法一kmp算法的啟發(fā)kmp算法的精髓是減少重復的計算，根據(jù)自身的位移匹配（特征），確定模式串的右移量?！痢蘻ababaabc正文ababaca模式1ababaca模式1babaab模式2主算法一（續(xù)）單詞前綴樹的使用和附加標記Okay模式串是構(gòu)成單詞前綴樹的基本元素模式“abcd”“bc”abccbdp也應該標記q附加標記附加標記傳遞性！主算法一（續(xù)）主過程abbabab正文：“abcbcabb……”abcbcabb找到匹配“bb”！主算法一（續(xù)）一點注意zababaabcbabaaaba主算法一（續(xù)）時間復雜性分析單詞前綴樹的構(gòu)建正文的檢索空間復雜性分析主算法一（續(xù)）優(yōu)化方案二進制轉(zhuǎn)化動態(tài)分配子結(jié)點+二分查找a01100001a01100001后綴樹概述路經(jīng)壓縮McCreight(1976),On-lineConstruction(1995)單詞：“ababc”abcbcabccabc主算法二單詞前綴樹的使用和擴展（TreeA）abbabab11111222主算法二（續(xù)）參數(shù)Shift，記錄每一個結(jié)點到達任意一個Okay結(jié)點（自身除外）的最短路徑（既可以通過樹中的邊，也可以通過前綴指針）主算法二（續(xù)）舉例abbabab11111222主算法二（續(xù)）后綴樹的使用和擴展(TreeB)由所有模式串倒置后的所有后綴組成。模式串為“abab”“ba”“bb”倒置：“baba”“ab”“bb”作用：在O(N)的時間內(nèi)，從后向

前地查看一段長度為N的字

符，檢測它是否為任意一個

模式串的子串a(chǎn)bbabab主算法二（續(xù)）TreeA上的函數(shù)ScanAFunctionScanA(Left,Right,P);如果Shift參數(shù)<最短的模式串長度div2，繼續(xù)讀入字符并且point繼續(xù)移動輸出所有遇到的匹配xxxxxxxxRightLeftxxxxP主算法二（續(xù)）TreeB上的函數(shù)ScanBFunctionScanB(Left,Right);在TreeB中，將T[Left..Right]從右向左進行掃描，檢查其是否為某個模式串的子串，返回最后掃描到的正文的位置。定義：

當一個字符串是某個模式串的子串時，稱其為“有效的”，反之為“無效的”。主算法二（續(xù)）主過程的基本思想：1、每次處理一個Left+1~Right的段落2、從Right向左通過ScanB檢索，最后到達位置pos。3、從pos到Right進行ScanA檢索。4、下一個過程的Left為ScanA檢索到的正文位置，Right為Left+當前TreeA上的結(jié)點的Shift參數(shù)主算法二（續(xù)）舉例模式串為

“abcd”和

“bcde”TreeAabcbcd653912478de編號123456789Shift432113214abcabcdecaRight主算法二（續(xù)）T=“abcabcde”，Left=0,Right=4,P=1從Right到Left+1逆向進行ScanB“a”為“有效的”“ca”為“無效的”，所以pos=4。Left+1模式串“abcd”“bcde”aaca沒出現(xiàn)pos主算法二（續(xù)）1..3的正文位置上，不可能出現(xiàn)模式的匹配ScanA的檢索需要從TreeA根結(jié)點重新開始，P指針重置為TreeA的根結(jié)點。

abcabcde從pos到Right進行ScanA檢索abcabcdeRight主算法二（續(xù)）posa主算法二（續(xù)）階段1：正向ScanA檢索字符串“a”abcbcd653912478de編號123456789Shift432113214PP23posabcabcdebcdRight主算法二（續(xù)）T=“abcabcde”

Left=4,Right=Left+Shift[P]=7,P=2從Right到Left+1逆向進行ScanB有“bcd”為“有效的”，所以pos=5。Left+1模式串“abcd”“bcde”bcdpos=L+1主算法二（續(xù)）階段1：正向ScanA檢索字符串“bcd”再讀入字符“e”abcbcd653912478de編號123456789Shift432113214P51PPP找到匹配“abcd”找到匹配“bcde”主算法二（續(xù)）時間復雜度分析：設(shè)最短的模式串長度為θ最壞情況O(N)設(shè)所有的模式串長度均為θ，θ足夠大時，若正文隨機。ScanB將所有的T[Left+1..Right]的字符掃描完畢的概率并不大，可以證明平均復雜度：算法總結(jié)——啟示1

的使用變大——ScanA將很難退出，平均復雜度變大！變小——Right-Left的差變小，ScanB的pos回到Left+1的可能性變大，平均復雜度變大！中間值！算法總結(jié)——啟示2優(yōu)劣得所的思想算術(shù)平均數(shù) —— 本算法幾何平均數(shù) —— Editor塊狀鏈表不斷更新的數(shù)組A[1..10000]，求max{A[1..i]}更新：O(10000)。取值：O(1)二叉樹（不易實現(xiàn)）max1[i]記錄A[1*100~(i-1)*100]中的最大值更新：O(100)。取值：O(100)啟示一條鐵鏈的強度，