




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
模式匹配第四章:串
主講:周翔樸素的模式匹配算法(BF算法)樸素的模式匹配算法思路:從主串s的第一個字符開始與t的第一個字符作比較;如果相等,繼續(xù)逐個比較后續(xù)的字符;如果不相等,使主串的第二個字符與t的第一個字符比較:如果相等,繼續(xù)逐個比較后續(xù)的字符;如果不相等,使主串的第三個字符與t的第一個字符比較:………以此類推,直到主串s的一個連續(xù)子串序列與模式t相等,返回子串序列在s串中的位置;否則匹配不成功,返回-1。樸素的模式匹配算法(BF算法)樸素的模式匹配算法思路:abecdecd主串s子串t從主串s的第一個字符開始與t的第一個字符作比較不相等從主串s的第二個字符開始與t的第一個字符作比較不相等從主串s的第三個字符開始與t的第一個字符作比較相等繼續(xù)比較后面的字符相等繼續(xù)比較后面的字符相等匹配成功樸素的模式匹配算法(BF算法)樸素的模式匹配算法(BF算法)KMP算法KMP算法(無回溯的模式匹配):KMP算法的主要思想就是利用已得到的部分匹配信息來進行后面的匹配過程,消除主串的回溯,從而提高匹配的效率。子串t主串scabxabeahycabdabKMP算法由匹配結(jié)果可以得出如下信息:t[0]=s[0];t[1]=s[1];t[0]!=t[1]==>t[0]!=s[1];t[0]=s[0];t[2]=s[2];t[0]!=t[2]==>t[0]!=s[2];t[0]=s[0];t[3]=s[3];t[0]=t[3]==>t[0]=s[3];
t[1]=s[1];t[4]=s[4];t[1]=t[4]==>t[1]=s[4];子串t主串scabxabeahycabdab因此下一次比較就比對s[5]與t[2]是否相等。這樣就省去了主串的回溯KMP算法KMP算法(無回溯的模式匹配):對于t的每個字符t[j](0<=j<=m-1),若存在一個整數(shù)k(k<j),使得模式t中k所指字符前的k個字符(t0t1…tk-1)依次與tj的前面k個字符(tj-ktj-k+1…tj-1)相同,并與主串s中i所指字符之前的k個字符相同,那么利用這種匹配信息就可以避免不必要的回溯。在匹配之前,用一個數(shù)組next來存放模式串t中字符的匹配信息,通過分析t中的字符,得出匹配完當(dāng)前字符后,下一次要匹配哪一個字符,將該字符信息存入next數(shù)組。存入next數(shù)組的這個值也稱為模式值、next值。KMP算法KMP算法(無回溯的模式匹配):next值的推導(dǎo)規(guī)則如下所示:(1)next[0]=-1:任何串中第一個字符的模式值規(guī)定為-1;(2)next[j]=1:模式串t中下標(biāo)為j的字符與首字符相同,且j之前的1-k個字符與開頭的1-k個字符不等(或者相等但t[k]=t[j])(1<=k<j);(3)next[j]=k:如果模式串t中下標(biāo)為j的字符之前k個字符與t開頭的k個字符相等,且t[j]!=t[k](1<=k<j),則next[j]=k;(4)next[j]=0:除(1)、(2)、(3)之外的其他情況next[j]都為0;KMP算法abcabd-100012bfbfbfkmpbf-10012340001KMP算法——分析總結(jié)本章主要講解了串的相關(guān)知識,包括串的概念、串的存儲結(jié)構(gòu)、以及串常用的模
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 學(xué)校校園電動自行車管理辦法
- 株洲師范高等專科學(xué)?!冻r韓國文學(xué)作品選讀》2023-2024學(xué)年第一學(xué)期期末試卷
- 浙江工業(yè)大學(xué)《高等代數(shù)(二)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024年內(nèi)蒙古鄂托克旗烏蘭鎮(zhèn)中學(xué)七年級數(shù)學(xué)第一學(xué)期期末學(xué)業(yè)水平測試試題含解析
- 安徽省阜陽市潁上縣2024-2025學(xué)年七上數(shù)學(xué)期末預(yù)測試題含解析
- 2025屆江蘇省南京市南京民辦育英第二外國語學(xué)校七年級數(shù)學(xué)第一學(xué)期期末考試模擬試題含解析
- 欽州幼兒師范高等??茖W(xué)?!稓W洲浪漫音樂派欣賞》2023-2024學(xué)年第一學(xué)期期末試卷
- 青島濱海學(xué)院《色彩構(gòu)成》2023-2024學(xué)年第一學(xué)期期末試卷
- 油氣地質(zhì)資料管理辦法
- 沼氣安全使用管理辦法
- 設(shè)備移交協(xié)議書模板
- 2025三季度四川經(jīng)準(zhǔn)檢驗檢測集團股份限公司招聘48人易考易錯模擬試題(共500題)試卷后附參考答案
- 網(wǎng)約車法律培訓(xùn)
- 深圳市羅湖區(qū)2025年小升初數(shù)學(xué)模擬試卷含解析
- 軸承加工合同協(xié)議
- 慢阻肺診療規(guī)范
- 2024-2025北師大版小學(xué)數(shù)學(xué)四年級上冊期末考試測試卷及參考答案(共三套)
- 黑龍江省普通高中2024年1月學(xué)業(yè)水平合格性考試 數(shù)學(xué)試題(真題)
- 《互聯(lián)網(wǎng)產(chǎn)品開發(fā)》教學(xué)教案
- 職業(yè)院校教師人工智能素養(yǎng):內(nèi)涵流變、框架構(gòu)建與生成路徑
- 校園信息化建設(shè)中的技術(shù)難題與解決方案
評論
0/150
提交評論