《工學(xué)第三章串》ppt課件(文件)
【正文】 １．樸素的模式匹配算法 該算法簡(jiǎn)稱 BF算法。 j=1。 j++。 //返回本趟匹配 else return 0。 while (i=S[0]amp。 } else { start++。 else return 0。 最壞的情況是： 主串前面 nm個(gè)位置都 部分匹配 到子串的最后一位，即這 nm位比較了 m次，別忘了最后 m位也各比較了一次，還要加上 m！ 所以總次數(shù)為：(nm)*m+m ＝ (nm+1)*m 不成功的匹配都發(fā)生在串 T的最后一個(gè)字符。 例： S=?a b a b c a b c a c b a b? T=?a b c a c? S=?a b a b c a b c a c b a b? T=?a b c a c? S=?a b a b c a b c a c b a b? T=?a b c a c? KMP最終的返回值應(yīng)為 i=6 需要討論兩個(gè)問(wèn)題： ①如何由 當(dāng)前部分匹配結(jié)果 確定模式向右滑動(dòng)的新比較起點(diǎn) k？ ② 模式應(yīng)該向右滑多遠(yuǎn)才是高效率的 ? i i i k k k i i 奇妙的結(jié)果： k 僅與模式串 T有關(guān)！ ② KMP算法的推導(dǎo)過(guò)程： 請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征： 兩式聯(lián)立可得： ‘ T1…T k1?=?Tj(k1) …T j1? S=?a b a b c a b c a c b a b? T=?a b c a c? i k 則 T的 k1～ 1位 ＝ S前 i1～ i(k1)位 設(shè)目前打算與 T的第 k字符開(kāi)始比較 (1) (2) ‘ T1…T k1? 則 T的 j1～ j(k1)位 ＝ S前 i1～ i(k1)位 i k j S=?a b a b c a b c a c b a b? T=?a b c a c? ‘ Tj(k1) …T j1? 截取一段，但 k有限制，1kj k是追求的新起點(diǎn) 加速的前提： T首與Tj1處有相同子串 注意： j 為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn) k。 即： next[j]越大，模式串向右滑動(dòng)得越遠(yuǎn) ，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越低（時(shí)間效率）。 j=2時(shí) , next[ j ]≡ 1； // 找不到 1kj的 k， 屬于“其他情況”； 剛才已歸納： j=3時(shí) , k={2}， 只需查看‘ T1?=?T2?成立否， No則屬于其他情況 j=4時(shí) , k={2， 3}， 要查看 ‘ T1?=?T3? 及 ‘ T1T2?=?T2 T3? 是否成立 j=5時(shí) , k={2， 3， 4}， 要查看‘ T1?=?T4? ， ?T1T2?=?T3T4? 和 ‘ T1T2T3?=?T2T3T4?是否成立 以此類推，可得后續(xù) next[j]值。 while (jT[0]) if ((k==0)| |(T[j]= =T[k])) { j++。 } 第 3章 特殊線性表 ——串 求模式串 T的 next函數(shù)值算法 第 3章 特殊線性表 ——串 求 next數(shù)組的算法只需將模式掃描一遍，設(shè)模式串的長(zhǎng)度為 m，則算法的時(shí)間復(fù)雜度為 O(m)。 30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任正教授。如果有人能在給定的期限內(nèi)解出任何一道難題，他將為那個(gè)人的博士論文簽名 (大約相當(dāng)于名譽(yù)導(dǎo)師吧 )！不知道世界之大，有沒(méi)有哪位后起之秀能獲得這樣的殊譽(yù)？ 。 他計(jì)劃共寫(xiě) 7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)Turing Award， 此時(shí)，他年僅 36歲。 KMP算法與 BF算法相比，增加了很大的難度，我們主要學(xué)習(xí)該算法的設(shè)計(jì)技巧。 next[j]=k。 j=1。 無(wú)首尾相同的子串時(shí) Next[j]的值為 1。 next[ j ]＝ 0 當(dāng) j＝ 1時(shí) //不比較 max { k | 1kj 且‘ T1…T k1?=?Tj(k1) …T j1? } 1 其他情況 討論： （ 1） next[ j ]的物理意義是什么？ （ 2） next[ j ]具體怎么求？ —即 KMP算法的實(shí)現(xiàn) 令 k = next[ j ]（ k 與 j 顯然具有函數(shù)關(guān)系），則 取 T首與 Tj1處最大的相同子串 新起點(diǎn) k怎么求？ （
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1