數(shù)據(jù)結構第4章串b教學ppt

1、1,1.令s=‘a(chǎn)aab’,t=‘a(chǎn)bcabaa’, u=‘a(chǎn)bcaabbabcabaacbacba’試分別求出它們的next函數(shù)值和nextval函數(shù)值2.已知主串s=‘ADBADABBAABADABBADADA’, 模式串pat=‘ADABBADADA’,寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程,布置第4章作業(yè)：,2,第4章 串（String）,4.1 串類型的定義4.2 串的表

2、示和實現(xiàn)4.3 串的模式匹配算法,,3,算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）,4.3 串的模式匹配算法,BF算法 （又稱古典的、經(jīng)典的、樸素的、窮舉的） KMP算法,算法種類：,,帶回溯，速度慢,避免回溯，匹配速度快，是全課程的亮點之一,定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos),4,BF算法的實現(xiàn)—即編寫Index(S, T, pos)函數(shù),例1： S=‘a(chǎn)babcabcacbab

3、’，T=‘a(chǎn)bcac’，pos=1， 求：串T在串S中第pos個字符之后的位置。,利用演示系統(tǒng)看BF算法執(zhí)行過程。,,BF算法設計思想：將主串S的第pos個字符和模式T的第1個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符； 若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。,直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，

4、返回值 0 .,5,Int Index(SString S, SString T, int pos) { i=pos; j=1; while ( iT[0]) return i-T[0]; //子串結束，說明匹配成功 else return0;}//Index,例2： S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，求Index(S,T,5) （參見教材P79）,,相當于子串

5、向右滑動一個字符位置,匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。,6,討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為,(n-m+1)*m＝O(n*m),,一般的情況是：O(n+m) 推導方法：要從最好到最壞情況統(tǒng)計總的比較次數(shù)，然后取平均。,BF算法的時間復雜度,最好的情況是：一配就中！ 只比較了m次。,能否加快子串（又稱模式串）的滑動速度？能！利用已部分匹配過的

6、信息使主串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算法設計思想② KMP算法的推導過程③ KMP算法的實現(xiàn) （關鍵技術:計算next[j]）④ KMP算法的時間復雜度,全書一大亮

7、點！,8,盡量利用已經(jīng)部分匹配的結果信息，盡量讓i不要回溯，加快模式串的滑動速度。例：,① KMP算法設計思想： (參見教材P80-84）,S=‘a(chǎn) b a b c a b c a c b a b’,T=‘a(chǎn) b c a c’,S=‘a(chǎn) b a b c a b c a c b a b’,T=‘a(chǎn) b c a c’,S=‘a(chǎn) b a b c a b c a c b a b’,T=‘a(chǎn) b c a c’,Index_kmp的返回值應為i=

8、6,需要討論兩個問題：①,a b a,a b c,i-T[0],如何由當前部分匹配結果確定模式向右滑動的新比較起點k？② 模式應該向右滑多遠才是高效率的?,9,奇妙的結果： k 僅與模式串T有關！,② KMP算法的推導過程：（見教材P81）,請抓住部分匹配時的兩個特征：,兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’,則T的k-1～1位＝S前i-1～i-(k-1)位 即(4-2）式

9、含義,設目前打算與T的第k字符開始比較,,(1),(2),‘T1…Tk-1’,則T的j-1～j-(k-1)位＝ S前i-1～i-(k-1)位 即(4-3）式含義,剛才肯定是在S的i處和T的第j字符 處失配,‘Tj-(k-1) …Tj-1’ 截取一段，但k有限制，1<k<j,k是追求的新起點,,加速的前提：T首與Tj處有相同子串,注意：j 為當前已知的失配位置，我們的目標是計算新起點

10、k。式中僅剩一個未知數(shù)k，理論上已可解！,10,根據(jù)模式串T的規(guī)律： ‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’由當前失配位置j(已知) ，可以歸納出計算新起點 k的表達式。,next[ j ]＝,0 當j＝1時 //不比較max { k | 1<k<j 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ }1 其他情況,,,討論：（1） next[ j

11、]的物理意義是什么？（2） next[ j ]具體怎么求？—即KMP算法的實現(xiàn),令k = next[ j ]（k 與j 顯然具有函數(shù)關系），則,,取T首與Tj處最大的相同子串,新起點 k怎么求？,11,（1） next[ j ]有何物理意義？,next[j]函數(shù)表征著模式T中最大相同前綴子串和后綴子串（真子串）的長度。可見，模式中相似部分越多，則next[j]函數(shù)越大，它既表示模式T字符之間的相關度越高，也表示j位置以前與主串部分

12、匹配的字符數(shù)越多。即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復雜度就越低（時間效率）。,next[ j ]＝max { k |1<k<j 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ },模式串從第1位往右直到K-1位,模式串從j的前一位往左經(jīng)過K-1位,想一想：如果主串和模式均為二進制碼流，用KMP算法效果如何？,T=‘a(chǎn) b a a b c a c’,再想一想：

13、如果主串是外存中一個大文件，用KMP算法效果又如何？,（2） next[ j ]具體怎么求？—即KMP算法的實現(xiàn),12,計算Next[j]的方法： 當j=1時，Next[j]=0； //Next[j]=0表示根本不進行字符比較當j>1時，Next[j]的值為：模式串的位置從1到j-1構成的串中所出現(xiàn)的首尾相同的子串的最大長度加1。無首尾相同的子串時Next[j]的值為1。 // Next[j]=1表示從模式串頭部開

14、始進行字符比較,（2） next[ j ]怎么計算？,怎樣計算模式T所有可能的失配點 j 所對應的 next[j]？,13,從兩頭往中間比較,模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8新匹配位k=next[j] :,0,,,1,1,2,2,3,1,2,討論：,,j=1時, next[ j ]≡ 0；//屬于“j=1”情況;j=2

15、時, next[ j ]≡ 1；// 找不到1<k<j的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’ 和

16、 ‘T1T2T3’=‘T2T3T4’,以此類推，可得后續(xù)next[j]值。,可用演示程序驗證,next[j]與s無關，可以預先計算,例：,14,下一個要討論的問題是：如何用遞推方式來求出最大相同子串的長度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個問題一旦解決，整個KMP算法就可以掌握得很透徹了。,void get_next(SString T, int &next[ ] ){ //

17、 //求模式串T的next函數(shù)值并存入數(shù)組next[ ]。i=1; next[1]=0; j=0;while(i<T[0] ){ if(j= = 0||T[i]= =T[j]){++i; ++j; next[i]=j;}else j=next[j]; }}// get_next,遞推法編程，參見教材P83程序,15,求解next[j]流程圖（遞推）,,注：遞歸與遞推的區(qū)別：,,遞推：由“小”到“大”遞

18、進； 遞歸：由“大”到“小”嵌套。,遞歸法（第1章自測卷4.2題）：long int fact(n) int n; { long f; if(n>1)f=n*fact(n-1); else f=1; return(f); },遞推法：fact=1; for ( i=1; i<=n; i++)fa

19、ct*= i;,例如：求f(n)=n!,17,第一步，先把模式T所有可能的失配點j 所對應的next[j]計算出來；第二步：執(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 ( iT[0]) return i

20、-T[0]; //子串結束，說明匹配成功 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 4 5 6 7 8 9,a a a a b,a a a a b

21、,a a a a b,,討論： next [ j ]是否完美無缺？,先用演示程序驗證,似乎慢了一點？能否再提速？,先計算next[j]：,此時效率不高的原因為：子串前4位相同時，主串字符若與其中一個不相等，則不必再與其余3個比較。而實際上還在依次比較。,a a a a b,19,void get_nextval(SString T, int &nextval[ ] ){ //next函數(shù)修正值存入數(shù)組nex

22、tvali=1; nextval[1]=0; j=0;while(i<T[0] ){ if(j= = 0||T[i]= =T[j] ){ ++i;++j;If(T[i]!=T[j] ) nextval[i]=j;else nextval[i]=nextval[j]; }else j=nextval[j]; }}// get_nextval,next函數(shù)的改進算法見教材P84算法4.8，稱為nextval

23、[ j ],,20,Int Index(SString S, SString T, int pos) { i=pos; j=1; while ( iT[0]) return i-T[0]; //子串結束，說明匹配成功 else return0;}//Index,例2： S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，求Index(S,T,5) （參見教材P79）,,相當于子串

24、向右滑動一個字符位置,匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。,21,第一步，先把模式T所有可能的失配點j 所對應的next[j]計算出來；第二步：執(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; w

25、hile ( iT[0]) return i-T[0]; //子串結束，說明匹配成功 else return0;}//Index_KMP,,22,void get_next(SString T, int &next[ ] ){ // //求模式串T的next函數(shù)值并存入數(shù)組next[ ]。i=1; next[1]=0; j=0;while(i<T[0] ){ if(j= = 0||T

26、[i]= =T[j]){++i; ++j; next[i]=j;}else j=next[j]; }}// get_next,遞推法編程，參見教材P83程序,23,void get_nextval(SString T, int &nextval[ ] ){ //next函數(shù)修正值存入數(shù)組nextvali=1; nextval[1]=0; j=0;while(i<T[0] ){ if(j

27、= = 0||T[i]= =T[j] ){ ++i;++j;If(T[i]!=T[j] ) nextval[i]=j;else nextval[i]=nextval[j]; }else j=nextval[j]; }}// get_nextval,next函數(shù)的改進算法見教材P84算法4.8，稱為nextval [ j ],,24,④ KMP算法的時間復雜度,注意：由于BF算法在一般情況下的時間復雜度也近似于O(n+m)，

28、所以至今仍被廣泛采用。,而此時KMP的情況是：由于指針i無須回溯，比較次數(shù)僅為n,即使加上計算next[j]時所用的比較次數(shù)m，比較總次數(shù)也僅為n+m=O(n＋m)，大大快于BF算法。,回顧BF的最惡劣情況：S與T之間存在大量的部分匹配，比較總次數(shù)為： (n-m+1)*m＝O(n*m),因為主串指針i不必回溯，所以從外存輸入文件時可以做到邊讀入邊查找——“流水作業(yè)” ！,KMP算法的用途：,第4章小結,串,,s =‘ a1a2 ……..