串的模式匹配算法.ppt

《串的模式匹配算法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第4章串（String）4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法1算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）4.3串的模式匹配算法BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法算法種類：帶回溯，速度慢避免回溯，匹配速度快，是全課程的亮點之一定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos)2BF算法的實現(xiàn)—即編寫Index(S,T,pos)函數(shù)例1：S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，pos=1，求：串T在串S中第pos個字符之后的位置。利用演示系統(tǒng)看BF算法執(zhí)行過程。BF算法設(shè)計

2、思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0.3討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)一般的情況是：O(n+m)推導(dǎo)方法：要從最好到最壞情況統(tǒng)計總的比較次數(shù)，然后取平均。BF算法的時間復(fù)雜度最好的情況是：一配就中！只比較了m次。能否加快子串

3、（又稱模式串）的滑動速度？能！利用已部分匹配過的信息使主串S的指針i不必回溯，最壞情況也能達到O(n+m)請看KMP算法！最壞的情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m＝(n-m+1)*m4KMP算法（特點：速度快）①KMP算法設(shè)計思想②KMP算法的推導(dǎo)過程③KMP算法的實現(xiàn)（關(guān)鍵技術(shù):計算next[j]）④KMP算法的時間復(fù)雜度全書一大亮點！5盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動速度。例：①KMP算法設(shè)計思想：

4、(參見教材P80-84）S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’Index_kmp的返回值應(yīng)為i=6需要討論兩個問題：①如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動的新比較起點k？②模式應(yīng)該向右滑多遠才是高效率的?iiikkabaabckiii-T[0]6奇妙的結(jié)果：k僅與模式串T有關(guān)?、贙MP算法的推導(dǎo)過程：（見教材P81）請抓住部分匹配時的兩個特征：兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’S=‘a(chǎn)babcabcacba

5、b’T=‘a(chǎn)bcac’ik則T的k-1～1位＝S前i-1～i-(k-1)位即(4-2）式含義設(shè)目前打算與T的第k字符開始比較(1)(2)‘T1…Tk-1’則T的j-1～j-(k-1)位＝S前i-1～i-(k-1)位即(4-3）式含義ikjS=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’剛才肯定是在S的i處和T的第j字符處失配‘Tj-(k-1)…Tj-1’截取一段，但k有限制，1

6、1…Tk-1’=‘Tj-(k-1)…Tj-1’由當(dāng)前失配位置j(已知)，可以歸納出計算新起點k的表達式。next[j]＝0當(dāng)j＝1時//不比較max{k

7、1

8、ext[j]函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復(fù)雜度就越低（時間效率）。next[j]＝max{k

9、1

10、計算Next[j]的方法：當(dāng)j=1時，Next[j]=0；//Next[j]=0