信息學(xué)-集訓(xùn)隊(duì)作業(yè)

市外國語學(xué)校[關(guān)鍵字]模式串單詞前綴樹后綴樹[KMP法以及后綴樹算法另外基于KMP算法的思想在第四章足于線性時(shí)間復(fù)雜度，接著在第六章提出了平均性能更好的算升到理論高度。 Knuth-Morris-Pratt 模式串的前綴函數(shù)（Prefix kmp 單詞查找樹（Trie） §4主算法一（線性算法 kmp McCreight 建立后綴樹（初步 后綴 §6主算法二（平均性能更好的算法 TreeATreeB §1§1.1所謂多串匹配，就是給定一些模式串，在一段文章（az26）中，找出第一個(gè)出現(xiàn)的任意一個(gè)模式串的位置。具體來說就是：mL1、L2……LmP1[1..L1]、P2[1..L2]……Pm[1..LmnT[1..n]，L100K,m1000,n900K 要找到一個(gè)最小的整數(shù)s[1,n]，滿a[1m]

注：如模式串為cdefg與efg，正文為abcdefgh時(shí)，會(huì)造成匹配目標(biāo)的不（§1.2ForFori1tonForj1tomDo 該算法從小到大枚舉每一個(gè)位置，并且進(jìn)行檢查情況下時(shí)間復(fù)雜度。O(nL)。 i1to XiPiT O(nLi內(nèi)完成。因此總復(fù)雜度為O(nmL)，可惜這兩種方法面對(duì)即將解決的數(shù)據(jù)量，是力不從心的應(yīng)該努力想出一種線性,或者更優(yōu)秀的算法。為此，要先介紹一個(gè)預(yù)備算法——，（Knuth-Morris-Pratt）§2Knuth-Morris-Pratt特————特操作，簡稱kmp算法?！?.1到所有的整數(shù)

對(duì)于x[1m]都有T[sx-1P[x§2.2模式串的前綴函數(shù)（Prefix對(duì)1im有前綴函數(shù)π(imaxj|P[1..jP[i-j1..i0Fori2tom k>0and End因?yàn)閗的增加值最多為m-1（最多進(jìn)行m-1“kk+1”）,所以“kπ[k]”m-1該程序段的復(fù)雜度為O(m)。§2.3kmp圖如圖2，當(dāng)在串中匹配到了“”的時(shí)候，可以根據(jù)π[5]=3，將模式串5-3=2（π進(jìn)行右移……。類似于計(jì)算前綴數(shù)組的方法，也不難寫出這段主算法的偽代碼Fori1ton q>0and writei-mEndIfEndFor與計(jì)算前綴函數(shù)的算法相同，qπ[q]的執(zhí)行次數(shù)不會(huì)超過n次。因此，整kmp算法的時(shí)間復(fù)雜度為O(nm)§3§3.1單詞查找樹（Trie）詞樹是一棵無限延伸的26叉樹。每個(gè)結(jié)點(diǎn)的26個(gè)通向子結(jié)點(diǎn)的邊，被分別命名a,b……z。對(duì)于每一個(gè)結(jié)點(diǎn)p，從根結(jié)點(diǎn)至p的路徑上的所有字母，可以連成一個(gè)字符串，定義這個(gè)字符串為Sp。反之，對(duì)于一個(gè)字符串S，根據(jù)該字符串上§3.2當(dāng)然實(shí)際情況下不能讓這棵單詞查找樹無限延伸因此在一棵初始3：aNILaNIL……zaNIL……bzaNIL……bzaNIL……zaaNIL……bzaNIL……b aNIL……zaNIL……bzaNIL……zp=Fori1tonp=Fori1ton NEWp->Child[S[i]];并對(duì)其初始pp-Endp->Child[ch](ch[a..zpch§3.3綴指針（PrefixPointerp找到最小的整數(shù)k[2,|Sp|，使得Sp[k..|Sp| b ab ppS b ab 考慮陰影結(jié)點(diǎn)p。Sp=abab。先找bab，不過這個(gè)字符串沒有在單詞樹中出現(xiàn)，因此再找ab，這一次找到了?！?.4雜度是可想而知的。仿照kmp算法中的前綴函數(shù)，不難想到，可以通過父結(jié)定義一個(gè)結(jié)點(diǎn)的前綴指針?biāo)赶虻慕Y(jié)點(diǎn)為該結(jié)點(diǎn)的前綴結(jié)點(diǎn)p q<>Rootandq->Child[ch]= qq- q->Child[ch]= p- p->Prefixq-5結(jié)點(diǎn)結(jié)點(diǎn) 結(jié)點(diǎn) b結(jié)點(diǎn)aappq1，q1bq1§4主算法一（線性算法§4.1kmpkmp移量當(dāng)然很想效仿這個(gè)算法對(duì)文章進(jìn)行僅一次掃描那么就需要當(dāng)6： a abababaca2個(gè)無奈的，也是很好的選擇。再加上kmp的前綴函數(shù)的啟發(fā)，就設(shè)計(jì)出了§3§4.2綴樹的基本元素根據(jù)§3提到的單詞前綴樹的建立方法可以把所有模串一棵空的樹，并且計(jì)算好它們的前綴。Paaa

處建立一個(gè)附加標(biāo)記（后面稱此標(biāo)記為Okay標(biāo)記Okay=aabcdbc7： bccqdp全。這個(gè)過程怎么彌補(bǔ)呢？不難發(fā)現(xiàn)q結(jié)點(diǎn)是p結(jié)點(diǎn)的前綴結(jié)點(diǎn)。因此想到OkayOkayOkay標(biāo)記?！?.3nP[1..n]piP[1..i]在單詞樹中對(duì)應(yīng)的結(jié)點(diǎn)那么證明p0(Root),p1……pn的前綴指針計(jì)算復(fù)雜度之和為O(n)。證設(shè)ci(0inpi結(jié)點(diǎn)的前綴指針的代價(jià)（c01。勢能函數(shù)將結(jié)點(diǎn)pi為一個(gè)實(shí)數(shù)Φ(i)(0in)，即結(jié)點(diǎn)pi的勢，在此定義Φ(0)0chq->p q<>Rootandq->Child[ch]= qq- q->Child[ch]=chq->p q<>Rootandq->Child[ch]= qq- q->Child[ch]= p- p->Prefixq-多為Φ(i1Φ(i1pi+1的前綴指針的代價(jià)ci1=1+“Φ(i2Φ(i1。對(duì)所有0in，將ci1nnci2nΦ(0)Φ(n)nO(n由此不難得出，整個(gè)單詞前綴樹的構(gòu)造時(shí)間復(fù)雜度為O(L)§4.4仿照kmp算法的主過程，的多串匹配算法也可以大功告成了AlgorithmAlgorithmMulti-PatternMaching1;預(yù)處理建立單詞前綴樹Fori1ton q≠Rootandq->Child[T[i]]= -EndFor注意，與kmp主算法相同，->Prefix的次數(shù)不會(huì)超過->Child[T[i]]的總次數(shù)，因此這一段程序的時(shí)間復(fù)雜度為O(n。babaazababaabcaba§4.5總時(shí)間復(fù)雜度為這兩部分的時(shí)間復(fù)雜度之和，為O(Ln所以在單詞樹中需要使用O(26L間，因此整個(gè)程序的空間復(fù)雜度為O(26L)§4.69a 01a01100001a01a01100001通過二分查找。這樣一來程序的時(shí)間復(fù)雜度將略有下降，但空間復(fù)雜度降為O(L)§5McCreight§5.1面已經(jīng)介紹過了。對(duì)于單詞“ababc10： bc

一共5個(gè)葉結(jié)點(diǎn)，分別代表了5個(gè)不同后綴（稱后綴對(duì)應(yīng)的結(jié)點(diǎn)為“終結(jié)點(diǎn)O(N2)級(jí)別（N為單詞的長度，那么其勢必會(huì)影響程序的運(yùn)行效率。改進(jìn)的思想是進(jìn)行路徑的壓縮，如11： c c 26個(gè)子結(jié)點(diǎn)，并且通向子結(jié)點(diǎn)的邊上O(N)級(jí)別。致在某條邊的中間出現(xiàn)了一個(gè)“終結(jié)點(diǎn)！這是很麻煩的，因此在原字符串如“$，來避免該情況的出現(xiàn)。§5.2S[1..n]，sufi=S[i..n]Si長的后綴。TpointTpointp提到p:Tpoint->String[‘a(chǎn)’..’z’,’$’]p§5.3建立后綴樹（初步McCreight算法用n步建立后綴樹T，T初始為空，第i步將sufiT。定義headi為sufi和sufj（1≤j＜i）的最長公共前綴中最長的。并定義sufi=headi+tailiForFori1tonNEWp->Child[taili[1]];p->String[taili[1]]EndS=“abab$ $ $ab$ 顯然，taili的時(shí)間復(fù)雜度僅為O(1)，因此找到headi對(duì)應(yīng)的結(jié)點(diǎn)位置，§5.4后綴性質(zhì)1headi-1可以寫成xx是一個(gè)可能為空的字符串，那么headi的前綴。j（j<i-1，滿足xsufj的前綴，那么sufj+1的前綴。又因?yàn)閟ufi的前綴，因此headi的前綴。后綴的定義p，其對(duì)應(yīng)的字符串可以寫成xx是一個(gè)字符，是一個(gè)可能為空的字符串。定義：p結(jié)點(diǎn)的后綴指針p->Suffix指向在樹中的位置（如果為空串，則指向根結(jié)點(diǎn)。定義根結(jié)點(diǎn)的后綴指向自 c c后綴的建立建立過程中使其滿足性質(zhì)2：每一個(gè)非葉結(jié)點(diǎn)在被創(chuàng)建后，其后綴立即被計(jì)算。1，不難得：后綴開始，向下檢索：ProcedureProcedureCount_Suffix_Link(p:Tpoint) p->Father到p q= s≠‘’ L=|s|and NEWr:Tpoint; ExitEnd EndWhileEnd3，(*)ss1的最長公§5.5headiheadi-1對(duì)應(yīng)結(jié)點(diǎn)的前綴指針開始，向下檢索ForFori1tonNEWq->Child[taili[1]];q->String[taili[1]] End時(shí)間復(fù)雜度分析1、3、4O(1)O(N)語句5，即所有非葉結(jié)點(diǎn)后綴的計(jì)算，因?yàn)镃ount_Suffix_Link的(*)處O(N)。2O(|headi|-|headi-1|+1)O(N)。McCreightO(N)?！?主算法二（平均性能更好的算法§6.1 為了適用主算法二，還需要在每一個(gè)結(jié)點(diǎn)增設(shè)一個(gè)參數(shù)Shift。它記錄每一也可以通過前綴指針，其中樹中的邊的權(quán)值為1，前綴指針的權(quán)值為0。這個(gè)Shift參數(shù)代表如果指針指向該結(jié)點(diǎn)，那么至少需要讀入多少字符，才有可能得ababbabb2 a1b OkayShiftShift參數(shù)的建立是很容易想到的，模式串Pi的第j個(gè)字符時(shí)，設(shè)newLij(1

jLi

(1Li如果建立了一個(gè)新結(jié)點(diǎn)p，那么p->Shift 如果達(dá)到了一個(gè)已經(jīng)存在的結(jié)點(diǎn)p，那么p->Shift min{p-僅僅這樣當(dāng)然是不夠的，因?yàn)檫€沒有考慮前綴。注意到前綴總是從下層指向上層因此進(jìn)行一次按照層號(hào)從小到大的遍歷并且對(duì)每個(gè)結(jié)點(diǎn)p：p->Shift min{p->Shift,p->Prefix->Shift}§6.2ababbabbbabaabbb15所示：aabb 注：與§5所述不同，在圖中，沒有出現(xiàn)含“$”的邊。這是因?yàn)楦鶕?jù)$§6.3TreeATreeBFunctionFunctionTreeApointT[L..R]，point point- 最短的模式串的長度div TreeA中，pointEndwrite過程所有遇到的所有Okay（遇到的所有匹配returnpointEnd2FunctionFunctionL。End這個(gè)過程如果返回了L，說明T[L..R]是某一個(gè)模式串的子串，否則不是。當(dāng)T[L..R]是某個(gè)模式串的子串時(shí) 稱其“有效的反之稱其“無效的§6.4AlgorithmAlgorithmMulti-PatternMachingTreeAL0; R最短的模式串的長度;pointTreeA.rootWhileR<=nposScanB(L+1, pointTreeA.root;(L,point)ScanA(pos,R,point);RL+point->ShiftEndWhileEnd在R之后。從R開始反向檢索（ScanB，設(shè)ScanB在pos處停止：如果pos=L+1，那么T[L+1..R]為“有效的因此可以正向（ScanA）L+1繼續(xù)往后檢索。pos>L+1T[L+1..pos-1]的每一個(gè)字符，均不可能成為某個(gè)匹配的模式串的串頭（L+1<=x<=pos-1T[x..R]必為“有效的，而ScanB的檢索終止在pos處，T[pos..R]是“有效的因此可以將point重置為TreeA的根結(jié)點(diǎn)，并pos往后檢索（ScanA。ScanA，ScanApoint->Shift>=div2”R-L>=最短的模式串的長度div2。圖16可以清楚地主算法二的工作順序 ScanA§6.5abbccddeabbccdde圖圖其中每個(gè)結(jié)點(diǎn)上的數(shù)字代表矩形為Okay結(jié)點(diǎn)他們的Shift參數(shù)如下123456789432113214T=“abcabcde階段1：L=0,R=4,capos=4pos>L+11..3的正文位置上，不可能出現(xiàn)模式的匹配，18： caTreeA上，從point=1開始，走過字符[pos..R]=“apoint=2。因?yàn)镾hift[2]=3>=最短的模式長度div2ScanApoint=2處停止。階段2：L=4,RL+Shift[point7,RL逆向進(jìn)行ScanBbcd”為“有效的ScanBpos=5處停止，pos=L+1，因此不用修改point值，直接正T[pos..R]進(jìn)行ScanA掃描，pointabcdScanA繼續(xù)掃描字符“epoint589，又發(fā)現(xiàn)一個(gè)匹配?！?.6單詞前綴樹和后綴樹的建立時(shí)間復(fù)雜度為O(26L（，，θ2當(dāng)所有的模式串長度均為θ，且θ足夠大時(shí)，若正文隨機(jī)，并且字母表足夠O(N)，下面將完成平均復(fù)雜度的計(jì)算和證明：θ，設(shè)

Lθkθk個(gè)較小的常數(shù)。設(shè)為字母表（alphabet）的大?。?6或者其它θ和夠大，可令其滿足log

M3θ即3k

θ2ScanBScanA的循環(huán)為一個(gè)階段命題 每一個(gè)階段中，R-L的數(shù)量級(jí)為O()Shift≥θdiv2R≥L+θdiv2R-L的數(shù)量級(jí)為O()。命題2 一共有最多O(n/)的階段。由命題1，這是顯然的。命題3 有不超過2k個(gè)“有效的”字符串命題 存在一個(gè)常數(shù)C，使得每讀入Clog個(gè)字符，其組成的字符串

1PM證明由命題3，有不超過2k個(gè)“有效的”字符串。而長度為Clog字符串有

讀入一個(gè)“有效的”字符串

1

C3k常數(shù)。根據(jù)條件有Clog2命題5ScanATreeAxp時(shí)，若對(duì)應(yīng)正文字T[y]T[y-x+1..y]必為“有效的證明T[y-x+1..y]TreeA.Rootp結(jié)命題 ScanA中，讀到Shift≥2

的結(jié)點(diǎn)并結(jié)束掃描，需要在[L..R]多讀入字符數(shù)的期望值為O(log)證明若在讀入前Clog個(gè)字符中，ScanAO(log。若在讀入Clog~2Clog的字符中，ScanAClogTreeApoint的深度必然大于等于（若小于 point->Shift，而Clog

5可得這Clog 的字符串是“有效的41MxClog~(x+1)Clog的字符中，ScanA。M 因此期望值小于(x1)Clog

O(log)命題7 每一個(gè)階段讀入字符數(shù)量的期望值為O(log)。證明分兩種情況1、ScanB讀入的字符數(shù)小于等于Clog41M

。ScanA將從TreeA的根結(jié)點(diǎn)開始，讀入最多ClogClog2

參數(shù)必然大于等于2

Clog2、ScanB讀完第Clog41ScanB的ScanA的MScanAShift參數(shù)不滿足而附加讀入的Clog個(gè)字符（6

1)2ClogM

1(2Clog)O(log)結(jié)論由命題2和命題7可得本算法的平均復(fù)雜度為O(nlog§7§7.1主算法二中使用了2

ScanA退出的標(biāo)志。R-L的長度下限。2如果2

變大，那么ScanA的退出將變得更因 是一個(gè)恰好使得平均復(fù)雜度取得最小值的中間點(diǎn)2§7.2多種算法并用（比如本題的單詞前綴樹和后綴樹）優(yōu)劣得