工學第三章串ppt課件-閱讀頁
2024-11-18 20:42本頁面
【正文】 T1…T k1?=?Tj(k1) …T j1? } 模式串從第 1位往右直到 K1位 模式串從 j的前一位往左經(jīng)過 K1位 想一想：如果主串和模式均為二進制碼流，用 KMP算法效果如何？ T=?a b a a b c a c? 再想一想：如果主串是外存中一個大文件，用 KMP算法效果又如何？ （ 2） next[ j ]具體怎么求？ —即 KMP算法的實現(xiàn) 計算 Next[j]的方法 ： ?當 j=1時， Next[j]=0； //Next[j]=0表示根本不進行字符比較 ?當 j1時， Next[j]的值為：模式串的位置 從 1到 j1構成的串中所出現(xiàn)的 首尾相同的子串 的最大長度 加 1。 // Next[j]=1表示從模式串頭部開始進行字符比較 （ 2） next[ j ]怎么計算？ 怎樣計算模式 T所有可能的失配點 j 所對應的 next[j]？ 從兩頭往中間比較 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 k=next[j] : next[ j ]＝ 0 當 j＝ 1時 max { k |1kj 且‘ T1…T k1?=?Tj(k1) …T j1? } 1 其他情況 0 1 2 2 3 1 2 討論： j=1時 , next[ j ]≡ 0； //屬于“ j=1”情況 。 next[j]與 s無關，可以預先計算 例： 1 第 3章 特殊線性表 ——串 1. 在串 S和串 T中分別設比較的起始下標 i和 j； 2. 循環(huán)直到 S中所剩字符長度小于 T的長度或 T中所有字符均比較完畢 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個字符；否則 將 j向右滑動到 next[j]位置 ， 即 j=next[j]； 如果 j=0， 則將 i和 j分別加 1， 準備下一趟比較； 3. 如果 T中所有字符均比較完畢，則返回匹配的起始下標；否則返回 0； KMP算法用偽代碼描述 void GetNext(char T[ ], int next[ ]) { next[1]=0。 k=0。 k++。 } else k=next[k]。而 KMP算法的時間復雜度為O(n+m)。 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c i j i j i j 第一趟， i=3， j=3失敗， i不動 next[3]=1， j滑動到 1的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第二趟 i=7， j=5失敗， i不動 next[5]=2， j滑動到 2的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第三趟， i=11， j=6， T中全部字符都比較完畢，匹配成功 第 3章 特殊線性表 特殊線性表 棧 隊 列 串 ⑴ 棧的定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 隊列定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 串的定義 ⑵ 基本概念 ⑶ ADT定義 順序棧 鏈 棧 循環(huán)隊列 鏈隊列 順序存儲 鏈接存儲 邏輯結構 存儲結構 邏輯結構 邏輯結構 存儲結構 存儲結構 比 較 模式匹配 比較 比較 ⑴ 基本操作的實現(xiàn) ⑵ 時間性能 ⑴ 基本操作的實現(xiàn) ⑵ 時間性能 第 3章 特殊線性表 1938年出生， 25歲畢業(yè)于加州理工學院數(shù)學系，博士，留校任教， 28歲時任副教授。從 31歲起，開始出版他的歷史性經(jīng)典巨著： The Art of Computer Programming。他有一個奇妙的承諾：在他定期進行的講座中，會不斷提出一些新
教學課件相關推薦
鄂ICP備17016276號-1