數(shù)據(jù)結(jié)構(gòu)第4章串B教學ppt.ppt

1、1,1.令s=aaab,t=abcabaa, u=abcaabbabcabaacbacba 試分別求出它們的next函數(shù)值和nextval函數(shù)值 2.已知主串s=ADBADABBAABADABBADADA, 模式串pat=ADABBADADA, 寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程,布置第4章作業(yè)：,2,第4章 串（String）,4.1 串類型的定義 4.2 串的表示和實現(xiàn) 4.3 串的模式匹配算法,3,算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）,4.3 串的模式匹配算法,BF算法 （又稱古典的、經(jīng)典的、樸素的、窮舉的） KMP算法,算法種類：,帶回溯

2、，速度慢,避免回溯，匹配速度快， 是全課程的亮點之一,定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos),4,BF算法的實現(xiàn)即編寫Index(S, T, pos)函數(shù),例1： S=ababcabcacbab，T=abcac，pos=1， 求：串T在串S中第pos個字符之后的位置。,利用演示系統(tǒng)看BF算法執(zhí)行過程。,BF算法設(shè)計思想： 將主串S的第pos個字符和模式T的第1個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符； 若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。,直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹

3、配成功。 否則，匹配失敗，返回值 0 .,5,Int Index(SString S, SString T, int pos) i=pos; j=1; while ( iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return0; /Index,例2： S=ababcabcacbab，T=abcac，求Index(S,T,5) （參見教材P79）,相當于子串向右滑動一個字符位置,匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。,6,討論： 若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為,(n-m+1)*mO(n*m),一

4、般的情況是：O(n+m) 推導方法：要從最好到最壞情況統(tǒng)計總的比較次數(shù)，然后取平均。,BF算法的時間復雜度,最好的情況是：一配就中！ 只比較了m次。,能否加快子串（又稱模式串）的滑動速度？ 能！利用已部分匹配過的信息使主串S的指針i不必回溯，最壞情況也能達到O(n+m),請看KMP算法！,最壞的情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m (n-m+1)*m,7,KMP算法（特點：速度快）, KMP算法設(shè)計思想 KMP算法的推導過程 KMP算法的實現(xiàn) （關(guān)鍵技術(shù):計算nextj） KM

5、P算法的時間復雜度,全書一大亮點！,8,盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動速度。 例：, KMP算法設(shè)計思想： (參見教材P80-84）,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,Index_kmp的返回值應(yīng)為i=6,需要討論兩個問題： ,a b a,a b c,i-T0,如何由當前部分匹配結(jié)果確定模式向右滑動的新比較起點k？ 模式應(yīng)該向右滑多遠才是高效率的?,9,奇

6、妙的結(jié)果： k 僅與模式串T有關(guān)！, KMP算法的推導過程：（見教材P81）,請抓住部分匹配時的兩個特征：,兩式聯(lián)立可得：T1Tk-1=Tj-(k-1) Tj-1,則T的k-11位S前i-1i-(k-1)位 即(4-2）式含義,設(shè)目前打算與T的第k字符開始比較,(1),(2),T1Tk-1,則T的j-1j-(k-1)位 S前i-1i-(k-1)位 即(4-3）式含義,剛才肯定是在S的i處和T的第j字符 處失配,Tj-(k-1) Tj-1 截取一段，但k有限制，1kj,k是追求的新起點,加速的前提：T首與Tj處有相同子串,注意：j 為當前已知的失配位置，我們的目標是計算新起點 k。 式中僅剩一個

7、未知數(shù)k，理論上已可解！,10,根據(jù)模式串T的規(guī)律： T1Tk-1=Tj-(k-1) Tj-1 由當前失配位置j(已知) ，可以歸納出計算新起點 k的表達式。,next j ,0 當j1時 /不比較 max k | 1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情況,討論： （1） next j 的物理意義是什么？ （2） next j 具體怎么求？即KMP算法的實現(xiàn),令k = next j （k 與j 顯然具有函數(shù)關(guān)系），則,取T首與Tj處最大的相同子串,新起點 k怎么求？,11,（1） next j 有何物理意義？,nextj函數(shù)表征著模式T中最大相同前綴子串和后綴子串（真子

8、串）的長度。 可見，模式中相似部分越多，則nextj函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。 即：nextj越大，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復雜度就越低（時間效率）。,next j max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 ,模式串從第1位往右直到K-1位,模式串從j的前一位往左經(jīng)過K-1位,想一想：如果主串和模式均為二進制碼流，用KMP算法效果如何？,T=a b a a b c a c,再想一想：如果主串是外存中一個大文件，用KMP算法效果又如何？,（2） next j 具體怎么求？即KMP算

9、法的實現(xiàn),12,計算Nextj的方法： 當j=1時，Nextj=0； /Nextj=0表示根本不進行字符比較 當j1時，Nextj的值為：模式串的位置從1到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長度加1。 無首尾相同的子串時Nextj的值為1。 / Nextj=1表示從模式串頭部開始進行字符比較,（2） next j 怎么計算？,怎樣計算模式T所有可能的失配點 j 所對應(yīng)的 nextj？,13,從兩頭往中間比較,模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位k=nextj :,0,1,1,2,2,3,1,2,討論：,j=1時,

10、 next j 0；/屬于“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ù)nextj值。,可用演示程序驗證,nextj與s無關(guān)，可以預先計算,例：,14,下一個要討論的問題是：如何用遞推方式來求出最大相同子串的長度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個問題一旦解決，整個

11、KMP算法就可以掌握得很透徹了。,void get_next(SString T, int / get_next,遞推法編程，參見教材P83程序,15,求解nextj流程圖（遞推）,注：遞歸與遞推的區(qū)別：,遞推：由“小”到“大”遞進； 遞歸：由“大”到“小”嵌套。,遞歸法（第1章自測卷4.2題）： long int fact(n) int n; long f; if(n1)f=n*fact(n-1); else f=1; return(f); ,遞推法： fact=1; for ( i=1; i=n; i+) fact*= i;,例如：求f(n)=n!,17,第一步，先把模式T所有可能的失配點

12、j 所對應(yīng)的nextj計算出來； 第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）, KMP算法的實現(xiàn)即Index( )操作的實現(xiàn),Int Index_KMP(SString S, SString T, int pos) /見教材P82 i=pos; j=1; while ( iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return0; /Index_KMP,前面定義的next函數(shù)在某些情況下還是有缺陷的， 例如模式aaaab與主串a(chǎn)aabaaaab匹配時的情況：,S: a a a b a a a a b,T: a a a a b,i: 1 2 3

13、 4 5 6 7 8 9,a a a a b,a a a a b,a a a a b,討論： next j 是否完美無缺？,先用演示程序驗證,似乎慢了一點？能否再提速？,先計算 nextj：,此時效率不高的原因為：子串前4位相同時，主串字符若與其中一個不相等，則不必再與其余3個比較。而實際上還在依次比較。,a a a a b,19,void get_nextval(SString T, int / get_nextval,next函數(shù)的改進算法見教材P84算法4.8， 稱為nextval j ,20,Int Index(SString S, SString T, int pos) i=pos;

14、 j=1; while ( iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return0; /Index,例2： S=ababcabcacbab，T=abcac，求Index(S,T,5) （參見教材P79）,相當于子串向右滑動一個字符位置,匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。,21,第一步，先把模式T所有可能的失配點j 所對應(yīng)的nextj計算出來； 第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）, KMP算法的實現(xiàn)即Index( )操作的實現(xiàn),Int Index_KMP(SString S, SString T, int

15、pos) /見教材P82 i=pos; j=1; while ( iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return0; /Index_KMP,22,void get_next(SString T, int / get_next,遞推法編程，參見教材P83程序,23,void get_nextval(SString T, int / get_nextval,next函數(shù)的改進算法見教材P84算法4.8， 稱為nextval j ,24, KMP算法的時間復雜度,注意：由于BF算法在一般情況下的時間復雜度也近似于O(n+m)，所以至今仍被廣泛采用。,而此時KMP的情況是：由于指針i無須回溯，比較次數(shù)僅為n,即使加上計算nextj時所用的比較次數(shù)m，比較總次數(shù)也僅為n+m=O(nm)，大大快于BF算法。,回顧BF的最惡劣情況：S與T之間存在大量的部分匹配，比較總次數(shù)為： (n-m+1)