資源描述：
《論文國家隊朱澤園》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、多串匹配算法及其啟示南京市外國語學(xué)校朱澤園［關(guān)鍵字］模式串單詞前綴樹后綴樹串匹配［摘要］字符串處理在實際應(yīng)用中具有重要地位，其看似簡單，但隨著研究的深入，各類思想精華涌現(xiàn)其中，難度也變得深不可測。因此信息學(xué)競賽中常以字符串處理為題，鍛煉選手的創(chuàng)新能力。本文第一章提出問題并進行樸素的分析，第二、三、五章分別介紹三個輔助算法：KMP模式匹配算法、自創(chuàng)的單詞前綴樹算法,以及后綴樹算法。另外基于KMP算法的核心思想，在第四章中，面向“多串匹配”問題提出一個線性算法。但本文并沒有滿足于線性時間復(fù)雜度，接著在第六章提出了平均
2、性能更好的算法。最后第七章對算法的構(gòu)思進行了剖析，并將這種思想方法上升到理論高度。第1頁共23頁［目錄］§1問題的提出§1.1§1.2問題描述最初想法§2Knuth-Morris-Pratt算法§2.1定義§2.2模式串的前綴函數(shù)（PrefixFunction）§2.3kmp主算法§3單詞前綴樹§3.1單詞查找樹（Trie）的定義§3.2單詞樹的建立§3.3前綴指針的定義§3.4前綴指針的生成§4主算法-（線性算法）§4.1kmp算法的啟發(fā)§4.2單詞前綴樹的使用及附加標(biāo)記§4.3單詞前綴樹的時間復(fù)雜度§4.4主
3、過程§4.5時空復(fù)雜度§4.6該算法的一些擴展§5后綴樹和McCreight算法§5.1數(shù)據(jù)結(jié)構(gòu)§5.2一些定義§5.3建立后綴樹（初步）§5.4后綴鏈接§5.5建立后綴樹§6主算法二（平均性能更好的算法）§6.1單詞前綴樹的使用和擴展§6.2后綴樹的使用和擴展§6.3TreeA和TreeB上的兩個函數(shù)§6.4主過程§6.5一個例子§6.6時間復(fù)雜度分析§7啟不和總結(jié)§7.1算法分析§7.2啟示§7.3總結(jié)第2頁共23頁[正文]§1問題的提出§1.1問題描述所謂多串匹配，就是給定一些模式串，在一段文章（只岀現(xiàn)小寫
4、a到z這26個字母）中，找出第一個出現(xiàn)的任意一個模式串的位置。具體來說就是：給定m個長度分別為Li.L2……L的模式串?dāng)?shù)組Pi[1..Li]>P2[l..L2]……PJ1..LJ,假設(shè)正文為一個長度為n的數(shù)組T[l..n],限定L5100K,m51000,n8900K。我們要找到一個最小的整數(shù)s[1,川，滿足a11,m]使得x[1,乙j都有T[s+x-l]=Pa[x]注：如模式串為cdefg與efg,正文為abcdefgh時，會造成匹配冃標(biāo)的不明確，因此我們一般將“求所有模式串的所有出現(xiàn)位置”這一任務(wù)模糊，轉(zhuǎn)而求
5、“第一個”（不過接下來將介紹的算法，可以在不改變復(fù)雜度的情況下完全接受此任務(wù)）。含邏輯關(guān)鍵字的搜索引擎是這個問題的實際應(yīng)用。醫(yī)學(xué)家們在DNA序列中，搜索可能為變開的兒種模式，也是這類問題的典型。因此用有效算法解決該問題能大大提髙各行各業(yè)的工作效率！§1.2最初想法最樸素的想法是：Fori<-1tonDoForj<-1tomDoIfi+Lj-l<=nThenKT[i..i+Li-l]=Pj[l..Lj]Then輸出位置i，并退出循環(huán)該算法從小到大枚舉每一個位置，并冃進行檢查。最壞情況下時間復(fù)雜度為O（n十L）o另一
6、個有效的優(yōu)化是：Fori1tomDoXi《Pi在t中第一次出現(xiàn)的位置，如果沒出現(xiàn)返回<-writemin（X）其小Pi在T中第一?次出現(xiàn)的位置，可以通過kmp算法（下一章將提到），在O（n+Li）內(nèi)完成。因此總復(fù)雜度為0（n十m+L）?？上н@兩種方法面對我們即將解決的數(shù)據(jù)量，是力不從心的，我們應(yīng)該努力想出一種線性，或者更優(yōu)秀的算法。為此，我們要先介紹一個預(yù)備算法——knip（Knuth-Morris-Pratt）單串匹配算法，和一個預(yù)備數(shù)據(jù)結(jié)構(gòu)單詞前綴樹。第3頁共23頁§2Knuth-Morris-Pratt算法
7、該算法為D.E.Knuth、J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的,被稱作“克努特——莫里斯一一普拉特操作”，簡稱kmp算法?！?.1定義給定一個長度為m的模式串P[l??m],和一個長度為n的正文T[l..n],找到所有的整數(shù)sfl,nm+11,滿足：對于x[1,m]都有T[s4-x-l]=P[x]o§2.2模式串的前綴函數(shù)(PrefixFunction)對18i8m有前綴函數(shù)^(i)=max{jIP[l..j]=P[bj+l.J]},如錯誤！鏈接無效。：06jSi圖1該函數(shù)可以通過如下程序段在數(shù)組
8、中完成預(yù)處理：k《0兀[1]《()Fori<-2tomdoWhilek>OandP[k+l]^P[i]Dok^n[k];IfP[k4-l]=P[i]ThenkGk+1;n[i]<-k;EndForfI123456-8910Pliababababcanhl00]2345601仇ababaabcaP6aba
9、bababababjab戶2abab(b)cajc[8]=6abc
