【正文】 i tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串 si …… 主串 S i tj 模式 T j tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串 第 3章 特殊線性表 ——串 1. 在串 S和串 T中設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 S中所剩字符個數(shù)小于 T的長度或 T的所有字符均比較完 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個字符；否則 將 i和 j回溯 ， 準(zhǔn)備下一趟比較； 3. 如果 T中所有字符均比較完 ， 則匹配成功 ， 返回匹配的起始比較下標(biāo)；否則 ， 匹配失敗 ， 返回 0； BF算法用偽代碼 : 第 3章 特殊線性表 ——串 int BF(char S[ ], char T[ ]) { i=1。 j++。 可見，模式中 相似部分越多，則 next[j]函數(shù)越大 ，它既表示 模式 T字符之間的相關(guān)度越高，也表示 j位置以前與主串 部分匹配 的字符數(shù)越多。 第 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章 特殊線性表 特殊線性表 棧 隊(duì) 列 串 ⑴ 棧的定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 隊(duì)列定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 串的定義 ⑵ 基本概念 ⑶ ADT定義 順序棧 鏈 棧 循環(huán)隊(duì)列 鏈隊(duì)列 順序存儲 鏈接存儲 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 存儲結(jié)構(gòu) 比 較 模式匹配 比較 比較 ⑴ 基本操作的實(shí)現(xiàn) ⑵ 時間性能 ⑴ 基本操作的實(shí)現(xiàn) ⑵ 時間性能 第 3章 特殊線性表 1938年出生， 25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士，留校任教， 28歲時任副教授。 } else k=next[k]。 如何確定模式的滑動距離？ 第 3章 特殊線性表 ——串 2． KMP算法 ① KMP算法設(shè)計(jì)思想 ② KMP算法的推導(dǎo)過程 ③ KMP算法的實(shí)現(xiàn) （ 關(guān)鍵技術(shù) :計(jì)算 next[j]） ④ KMP算法的時間復(fù)雜度 第 3章 特殊線性表 ——串 ① KMP算法設(shè)計(jì)思想： 盡量利用已經(jīng) 部分匹配 的結(jié)果信息，盡量讓 i不要回溯，加快模式串的滑動速度。start=1。下面我們介紹兩種串的模式匹配算法。 ⑼ StrRep (s， t， r)： 串替換 ， 在串 s中用串 r替換所有與串 t相等的子串 。擴(kuò)展 ASCII碼由 8 位二進(jìn)制數(shù)表示一個字符，總共可以表示 256 個字符，足夠表示英語和一些特殊符號，但無法滿足國際需要。 第 3章 特殊線性表 ——串 串的邏輯結(jié)構(gòu) 1. 串的定義 串是零個或多個字符組成的有限序列 。 注意不是符號 ， 串的數(shù)據(jù)元素均取自某個字符集 。 若 t不是 s的子串 ， 則返回 0。 T稱為模式 。 //返回本趟匹配 else return 0。 最壞的情況是： 主串前面 nm個位置都 部分匹配 到子串的最后一位，即這 nm位比較了 m次，別忘了最后 m位也各比較了一次，還要加上 m！ 所以總次數(shù)為：(nm)*m+m ＝ (n