數(shù)據(jù)結(jié)構(gòu)第4章串b教學(xué)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’,寫(xiě)出模式串的nextval函數(shù)值，并由此畫(huà)出KMP算法匹配的全過(guò)程,布置第4章作業(yè)：,2,第4章 串（String）,4.1 串類型的定義4.2 串的表

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

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

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

5、向右滑動(dòng)一個(gè)字符位置,匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。,6,討論：若n為主串長(zhǎng)度，m為子串長(zhǎng)度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為,(n-m+1)*m＝O(n*m),,一般的情況是：O(n+m) 推導(dǎo)方法：要從最好到最壞情況統(tǒng)計(jì)總的比較次數(shù)，然后取平均。,BF算法的時(shí)間復(fù)雜度,最好的情況是：一配就中！ 只比較了m次。,能否加快子串（又稱模式串）的滑動(dòng)速度？能！利用已部分匹配過(guò)的

6、信息使主串S的指針i不必回溯，最壞情況也能達(dá)到O(n+m),,請(qǐng)看KMP算法！,最壞的情況是：主串前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m ＝(n-m+1)*m,7,KMP算法（特點(diǎn)：速度快）,① KMP算法設(shè)計(jì)思想② KMP算法的推導(dǎo)過(guò)程③ KMP算法的實(shí)現(xiàn) （關(guān)鍵技術(shù):計(jì)算next[j]）④ KMP算法的時(shí)間復(fù)雜度,全書(shū)一大亮

7、點(diǎn)！,8,盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動(dòng)速度。例：,① KMP算法設(shè)計(jì)思想： (參見(jiàn)教材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的返回值應(yīng)為i=

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

9、含義,設(shè)目前打算與T的第k字符開(kāi)始比較,,(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是追求的新起點(diǎn),,加速的前提：T首與Tj處有相同子串,注意：j 為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn)

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

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

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

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

14、始進(jìn)行字符比較,（2） next[ j ]怎么計(jì)算？,怎樣計(jì)算模式T所有可能的失配點(diǎn) j 所對(duì)應(yīng)的 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時(shí), next[ j ]≡ 0；//屬于“j=1”情況;j=2

15、時(shí), next[ j ]≡ 1；// 找不到1<k<j的k，屬于“其他情況”；,剛才已歸納：,j=3時(shí), k={2}，只需查看‘T1’=‘T2’成立否，No則屬于其他情況,j=4時(shí), k={2，3}，要查看‘T1’=‘T3’ 及‘T1T2’=‘T2 T3’ 是否成立,j=5時(shí), k={2，3，4}，要查看‘T1’=‘T4’ ，‘T1T2’=‘T3T4’ 和

16、 ‘T1T2T3’=‘T2T3T4’,以此類推，可得后續(xù)next[j]值。,可用演示程序驗(yàn)證,next[j]與s無(wú)關(guān)，可以預(yù)先計(jì)算,例：,14,下一個(gè)要討論的問(wèn)題是：如何用遞推方式來(lái)求出最大相同子串的長(zhǎng)度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個(gè)問(wèn)題一旦解決，整個(gè)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,遞推法編程，參見(jiàn)教材P83程序,15,求解next[j]流程圖（遞推）,,注：遞歸與遞推的區(qū)別：,,遞推：由“小”到“大”遞

18、進(jìn)； 遞歸：由“大”到“小”嵌套。,遞歸法（第1章自測(cè)卷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所有可能的失配點(diǎn)j 所對(duì)應(yīng)的next[j]計(jì)算出來(lái)；第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）,③ KMP算法的實(shí)現(xiàn)—即Index( )操作的實(shí)現(xiàn),Int Index_KMP(SString S, SString T, int pos) { //見(jiàn)教材P82 i=pos; j=1; while ( iT[0]) return i

20、-T[0]; //子串結(jié)束，說(shuō)明匹配成功 else return0;}//Index_KMP,,前面定義的next函數(shù)在某些情況下還是有缺陷的，例如模式aaaab與主串a(chǎn)aabaaaab匹配時(shí)的情況：,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 ]是否完美無(wú)缺？,先用演示程序驗(yàn)證,似乎慢了一點(diǎn)？能否再提速？,先計(jì)算next[j]：,此時(shí)效率不高的原因?yàn)椋鹤哟?位相同時(shí)，主串字符若與其中一個(gè)不相等，則不必再與其余3個(gè)比較。而實(shí)際上還在依次比較。,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ù)的改進(jìn)算法見(jiàn)教材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]; //子串結(jié)束，說(shuō)明匹配成功 else return0;}//Index,例2： S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，求Index(S,T,5) （參見(jiàn)教材P79）,,相當(dāng)于子串

24、向右滑動(dòng)一個(gè)字符位置,匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。,21,第一步，先把模式T所有可能的失配點(diǎn)j 所對(duì)應(yīng)的next[j]計(jì)算出來(lái)；第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）,③ KMP算法的實(shí)現(xiàn)—即Index( )操作的實(shí)現(xiàn),Int Index_KMP(SString S, SString T, int pos) { //見(jiàn)教材P82 i=pos; j=1; w

25、hile ( iT[0]) return i-T[0]; //子串結(jié)束，說(shuō)明匹配成功 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,遞推法編程，參見(jiàn)教材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ù)的改進(jìn)算法見(jiàn)教材P84算法4.8，稱為nextval [ j ],,24,④ KMP算法的時(shí)間復(fù)雜度,注意：由于BF算法在一般情況下的時(shí)間復(fù)雜度也近似于O(n+m)，

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