數(shù)據(jù)結(jié)構(gòu)第4章串B教學(xué)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 串的表示和實(shí)現(xiàn) 4.3 串的模式匹配算法,3,算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）,4.3 串的模式匹配算法,BF算法 （又稱古典的、經(jīng)典的、樸素的、窮舉的） KMP算法,算法種類：,帶回溯

2、，速度慢,避免回溯，匹配速度快， 是全課程的亮點(diǎn)之一,定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos),4,BF算法的實(shí)現(xiàn)即編寫Index(S, T, pos)函數(shù),例1： S=ababcabcacbab，T=abcac，pos=1， 求：串T在串S中第pos個(gè)字符之后的位置。,利用演示系統(tǒng)看BF算法執(zhí)行過程。,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)，即匹

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）,相當(dāng)于子串向右滑動(dòng)一個(gè)字符位置,匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。,6,討論： 若n為主串長(zhǎng)度，m為子串長(zhǎng)度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為,(n-m+1)*mO(n*m),一

4、般的情況是：O(n+m) 推導(dǎo)方法：要從最好到最壞情況統(tǒng)計(jì)總的比較次數(shù)，然后取平均。,BF算法的時(shí)間復(fù)雜度,最好的情況是：一配就中！ 只比較了m次。,能否加快子串（又稱模式串）的滑動(dòng)速度？ 能！利用已部分匹配過的信息使主串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)過程 KMP算法的實(shí)現(xiàn) （關(guān)鍵技術(shù):計(jì)算nextj） KM

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

6、妙的結(jié)果： k 僅與模式串T有關(guān)！, KMP算法的推導(dǎo)過程：（見教材P81）,請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：,兩式聯(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是追求的新起點(diǎn),加速的前提：T首與Tj處有相同子串,注意：j 為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn) k。 式中僅剩一個(gè)

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

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

9、法的實(shí)現(xiàn),12,計(jì)算Nextj的方法： 當(dāng)j=1時(shí)，Nextj=0； /Nextj=0表示根本不進(jìn)行字符比較 當(dāng)j1時(shí)，Nextj的值為：模式串的位置從1到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長(zhǎng)度加1。 無首尾相同的子串時(shí)Nextj的值為1。 / Nextj=1表示從模式串頭部開始進(jìn)行字符比較,（2） next j 怎么計(jì)算？,怎樣計(jì)算模式T所有可能的失配點(diǎn) j 所對(duì)應(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時(shí),

10、 next j 0；/屬于“j=1”情況; j=2時(shí), next j 1；/ 找不到1kj的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 和 T1T2T3=T2T3T4,以此類推，可得后續(xù)nextj值。,可用演示程序驗(yàn)證,nextj與s無關(guān)，可以預(yù)先計(jì)算,例：,14,下一個(gè)要討論的問題是：如何用遞推方式來求出最大相同子串的長(zhǎng)度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個(gè)問題一旦解決，整個(gè)

11、KMP算法就可以掌握得很透徹了。,void get_next(SString T, int / get_next,遞推法編程，參見教材P83程序,15,求解nextj流程圖（遞推）,注：遞歸與遞推的區(qū)別：,遞推：由“小”到“大”遞進(jìn)； 遞歸：由“大”到“小”嵌套。,遞歸法（第1章自測(cè)卷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所有可能的失配點(diǎn)

12、j 所對(duì)應(yīng)的nextj計(jì)算出來； 第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）, KMP算法的實(shí)現(xiàn)即Index( )操作的實(shí)現(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匹配時(shí)的情況：,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 是否完美無缺？,先用演示程序驗(yàn)證,似乎慢了一點(diǎn)？能否再提速？,先計(jì)算 nextj：,此時(shí)效率不高的原因?yàn)椋鹤哟?位相同時(shí)，主串字符若與其中一個(gè)不相等，則不必再與其余3個(gè)比較。而實(shí)際上還在依次比較。,a a a a b,19,void get_nextval(SString T, int / get_nextval,next函數(shù)的改進(jìn)算法見教材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）,相當(dāng)于子串向右滑動(dòng)一個(gè)字符位置,匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。,21,第一步，先把模式T所有可能的失配點(diǎn)j 所對(duì)應(yīng)的nextj計(jì)算出來； 第二步：執(zhí)行定位函數(shù)Index_kmp （與BF算法模塊非常相似）, KMP算法的實(shí)現(xiàn)即Index( )操作的實(shí)現(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ù)的改進(jìn)算法見教材P84算法4.8， 稱為nextval j ,24, KMP算法的時(shí)間復(fù)雜度,注意：由于BF算法在一般情況下的時(shí)間復(fù)雜度也近似于O(n+m)，所以至今仍被廣泛采用。,而此時(shí)KMP的情況是：由于指針i無須回溯，比較次數(shù)僅為n,即使加上計(jì)算nextj時(shí)所用的比較次數(shù)m，比較總次數(shù)也僅為n+m=O(nm)，大大快于BF算法。,回顧BF的最惡劣情況：S與T之間存在大量的部分匹配，比較總次數(shù)為： (n-m+1)