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