第六講-kmp算法-棧(已修改)
2025-08-17 10:58 本頁面
【正文】 Hu JunfengPeking UniversityKMP算法、棧及其應(yīng)用2022/03/101Hu JunfengPeking University助教負責(zé)安排：王磊 ： 0051102700611065彭躍輝： 0071100300711049鄧昌明： 0071105100711076馬秀娟： 0071107800711114劉 亮： 00711115–00724079Email:負責(zé)助教 上機：前三組， 4號機房。后兩組 5號機房。2Hu JunfengPeking University內(nèi)容：? 作業(yè)補充題講解? KMP算法? 棧及其應(yīng)用3Hu JunfengPeking University循環(huán)鏈表排序（冒泡法）4Hu JunfengPeking University 5Hu JunfengPeking University循環(huán)鏈表排序6Hu JunfengPeking University關(guān)于程序的白盒調(diào)試? 明確算法思路? 分步? 分層? 隔離? 考察邊界點7Hu JunfengPeking University無回溯的模式匹配方法 (KMP算法 )? 基本思想? 無回溯的模式匹配算法? 匹配算法的時間效率分析? Next數(shù)組計算8Hu JunfengPeking University基本思想 1? 要找到一個無回溯的模式匹配算法，關(guān)鍵在于當匹配過程中，一旦 pi與 tj比較不等，即：SubStr_Seq(p,1,i1)=SubStr_Seq(t,ji+1,i1)pi≠tj? 要能立即確定 p右移的位數(shù)和繼續(xù)（無回溯）比較的字符，也就是說 應(yīng)該用 p中的哪個字符和 tj進行比較 ？把這個字符記為 pk，顯然有 ki，并且對于不同的 i， k值也不同。 9Hu JunfengPeking UniversityKMP算法 —— 特征子串與 next數(shù)組S0 S1 Sji … Sj1 Sj Sj+1 …P0 P1 … Pi1 Pi Pi+1 …next[0] next[1] next[2] … next[i1] next[i] …Xk (1) 求 p0…pi1 中最大相同的前綴和后綴的長度 k。 (2) next[i] = k。 作為特殊情況，當 i=0時，令 next[i] = 1。 顯然，對于任意 i(0≤im)，有 next[i] i。 next[i]的值越小，意味著在 Sj不回溯的情況下，模式串 P向右移動的越多。10Hu JunfengPeking University基本思想 2? 第 i個位置的特征值 k僅依賴于模式 p本身前 i個字符的組成，而與目標 t無關(guān) ，一般可用 next[i]表示與 i對應(yīng)的 k值。其意義在于：– 若 next[i]≥0，表示一旦匹配過程中 pi與 tj比較不等，可用 p中以 next[i]為下標的字符與 tj進行比較。– 若 next[i]=1，則表示 p中任何字符都不必在與 tj進行比較，下次比較從 tj+1與 p0開始。? 對于任意模式 p，只要我們能夠確定 next[i](i=0,1,…,m1)的值，就可以加速匹配過程，避免回溯問題。當 tj≠pi時，直接右移 inext[i]個字符，并從 tj(或 tj+1)繼續(xù)下去。11Hu JunfengPeking UniversityKMP算法：12Hu JunfengPeking University模式串的特征數(shù)與特征向量? 模式串 P開頭的任意個字符，把它稱為前綴子串。p0p1p2…p m1? 在 P的第 i位置的左邊，取出 k個字符，稱為 i位置的左子串。 pik+1... pi2 pi1 pi? 求出最長的（最大的 k）使得前綴子串與左子串相匹配稱為，在第 i位的最長前綴串。? 第 i位的最長前綴串的長度 k就是模板串 P在位置 i上的 特征數(shù) n[i]? 特征數(shù)組成的向量稱為該模式串的 特征向量 。13Hu JunfengPeking UniversityNext數(shù)組（特征向量）的計算? 下面證明對于任意的模式串 p=p0p1…p m1,確實存在一個由模式串本身唯一確定的與目標串無關(guān)的數(shù)組 next，并給出next數(shù)組的計算方法。? 在 p與任意的目標串 t匹配時，若發(fā)現(xiàn) tj≠pi，則意味著 p0、p … 、 pi1已經(jīng)與 t中對應(yīng)的字符進行過比較，而且是相等的，否則輪不到 tj與 pi的比較，因此下面兩個圖是等價的。t0… tji tji+1 … t j1 tj …p0 … p i1 pi…t0…t ji1
電大資料相關(guān)推薦
鄂ICP備17016276號-1