資源描述：
《國家集訓(xùn)隊(duì)2004論文集 朱澤園》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、IOI2004國家集訓(xùn)隊(duì)論文朱澤園多串匹配算法及其啟示南京市外國語學(xué)校朱澤園[關(guān)鍵字]模式串單詞前綴樹后綴樹串匹配[摘要]字符串處理在實(shí)際應(yīng)用中具有重要地位，其看似簡(jiǎn)單，但隨著研究的深入，各類思想精華涌現(xiàn)其中，難度也變得深不可測(cè)。因此信息學(xué)競(jìng)賽中常以字符串處理為題，鍛煉選手的創(chuàng)新能力。本文第一章提出問題并進(jìn)行樸素的分析，第二、三、五章分別介紹三個(gè)輔助算法：KMP模式匹配算法、自創(chuàng)的單詞前綴樹算法，以及后綴樹算法。另外基于KMP算法的核心思想，在第四章中，面向“多串匹配”問題提出一個(gè)線性算法。但本文并沒有滿足于線性時(shí)間復(fù)雜度，接著在第六章提出了平均性能更好的算法。最后第七章對(duì)算法的構(gòu)
2、思進(jìn)行了剖析，并將這種思想方法上升到理論高度。第1頁共23頁IOI2004國家集訓(xùn)隊(duì)論文朱澤園[目錄]§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單詞前綴樹的時(shí)間復(fù)雜度§4.4主過程§4.5時(shí)空復(fù)雜度§4.6該算法的一些擴(kuò)展§5后綴樹和McCreig
3、ht算法§5.1數(shù)據(jù)結(jié)構(gòu)§5.2一些定義§5.3建立后綴樹（初步）§5.4后綴鏈接§5.5建立后綴樹§6主算法二（平均性能更好的算法）§6.1單詞前綴樹的使用和擴(kuò)展§6.2后綴樹的使用和擴(kuò)展§6.3TreeA和TreeB上的兩個(gè)函數(shù)§6.4主過程§6.5一個(gè)例子§6.6時(shí)間復(fù)雜度分析§7啟示和總結(jié)§7.1算法分析§7.2啟示§7.3總結(jié)第2頁共23頁IOI2004國家集訓(xùn)隊(duì)論文朱澤園[正文]§1問題的提出§1.1問題描述所謂多串匹配，就是給定一些模式串，在一段文章（只出現(xiàn)小寫a到z這26個(gè)字母）中，找出第一個(gè)出現(xiàn)的任意一個(gè)模式串的位置。具體來說就是：給定m個(gè)長(zhǎng)度分別為L(zhǎng)1、L2……
4、Lm的模式串?dāng)?shù)組P1[1..L1]、P2[1..L2]……Pm[1..Lm]，假設(shè)正文為一個(gè)長(zhǎng)度為n的數(shù)組T[1..n]，限定?L￡100K,m￡1000,n￡900K。我們要找到一個(gè)最小的整數(shù)s?[1,n]，滿足$a?[1,m]使得"x?[1,La]都有T[s+x-1]=Pa[x]注：如模式串為cdefg與efg，正文為abcdefgh時(shí)，會(huì)造成匹配目標(biāo)的不明確，因此我們一般將“求所有模式串的所有出現(xiàn)位置”這一任務(wù)模糊，轉(zhuǎn)而求“第一個(gè)”（不過接下來將介紹的算法，可以在不改變復(fù)雜度的情況下完全接受此任務(wù)）。含邏輯關(guān)鍵字的搜索引擎是這個(gè)問題的實(shí)際應(yīng)用。醫(yī)學(xué)家們?cè)贒NA序列中，搜索可能
5、為變異的幾種模式，也是這類問題的典型。因此用有效算法解決該問題能大大提高各行各業(yè)的工作效率！§1.2最初想法最樸素的想法是：Fori?1tonDoForj?1tomDoIfi+Lj-1<=nThenIfT[i..i+Lj-1]=Pj[1..Lj]Then輸出位置i，并退出循環(huán)該算法從小到大枚舉每一個(gè)位置，并且進(jìn)行檢查。最壞情況下時(shí)間復(fù)雜度為O(n×?L)。另一個(gè)有效的優(yōu)化是：Fori?1tomDoXi?Pi在T中第一次出現(xiàn)的位置，如果沒出現(xiàn)返回∞writemin(X)其中Pi在T中第一次出現(xiàn)的位置，可以通過kmp算法（下一章將提到），在O(n+Li)內(nèi)完成。因此總復(fù)雜度為O(n×m
6、+?L)?？上н@兩種方法面對(duì)我們即將解決的數(shù)據(jù)量，是力不從心的，我們應(yīng)該努力想出一種線性,或者更優(yōu)秀的算法。為此，我們要先介紹一個(gè)預(yù)備算法——kmp（Knuth-Morris-Pratt）單串匹配算法，和一個(gè)預(yù)備數(shù)據(jù)結(jié)構(gòu)——單詞前綴樹。第3頁共23頁IOI2004國家集訓(xùn)隊(duì)論文朱澤園§2Knuth-Morris-Pratt算法該算法為D.E.Knuth、J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)的，被稱作“克努特——莫里斯——普拉特操作”，簡(jiǎn)稱kmp算法?！?.1定義給定一個(gè)長(zhǎng)度為m的模式串P[1..m]，和一個(gè)長(zhǎng)度為n的正文T[1..n]，找到所有的整數(shù)s?[1,n-m+1
7、]，滿足：對(duì)于"x?[1,m]都有T[s+x-1]=P[x]?！?.2模式串的前綴函數(shù)（PrefixFunction）對(duì)1￡i￡m有前綴函數(shù)π(i)=max{j
8、P[1..j]=P[i-j+1..i]}，如錯(cuò)誤！鏈接無效。：0￡j￡i圖1該函數(shù)可以通過如下程序段在數(shù)組中完成預(yù)處理：k?0π[1]?0Fori?2tomdoWhilek>0andP[k+1]≠P[i]Dok?π[k];IfP[k+1]=P[i]Thenk?k+1;π[i]?k;EndFor第4頁共23頁I
