串的模式匹配算法

1、串的模式匹配算法1第1頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位） 4.3 串的模式匹配算法 BF算法 （又稱(chēng)古典的、經(jīng)典的、樸素的、窮舉的） KMP算法算法種類(lèi)：帶回溯，速度慢避免回溯，匹配速度快，是全課程的亮點(diǎn)之一定位問(wèn)題稱(chēng)為串的模式匹配，典型函數(shù)為Index(S,T,pos)2第2頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日BF算法的實(shí)現(xiàn)即編寫(xiě)Index(S, T, pos)函數(shù)例1： S=ababcabcacbab，T=abcac，pos=1， 求：串T在串S中第pos個(gè)字符之后的位置。 利用演示系統(tǒng)看BF算法

2、執(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)，即匹配成功。否則，匹配失敗，返回值 0 .3第3頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日討論：若n為主串長(zhǎng)度，m為子串長(zhǎng)度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*mO(n*m)一般的情況是：O(n+m) 推導(dǎo)方法：要從最好到最壞情況統(tǒng)計(jì)總的比較次數(shù)，然后取平均。BF算法的時(shí)間復(fù)雜

3、度最好的情況是：一配就中！ 只比較了m次。能否加快子串（又稱(chēng)模式串）的滑動(dòng)速度？能！利用已部分匹配過(guò)的信息使主串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)*m4第4頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日KMP算法（特點(diǎn)：速度快） KMP算法設(shè)計(jì)思想 KMP算法的推導(dǎo)過(guò)程 KMP算法的實(shí)現(xiàn) （關(guān)鍵技術(shù):計(jì)算nextj） KMP算法的時(shí)間復(fù)雜度全書(shū)一大亮點(diǎn)！5第5頁(yè)，共21頁(yè)，2022

4、年，5月20日，5點(diǎn)57分，星期日盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動(dòng)速度。例： KMP算法設(shè)計(jì)思想： (參見(jiàn)教材P80-84）S=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cIndex_kmp的返回值應(yīng)為i=6需要討論兩個(gè)問(wèn)題：如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)k？ 模式應(yīng)該向右滑多遠(yuǎn)才是高效率的?iiikk a b aa b ckiii-T06第6頁(yè)，共21頁(yè)，202

5、2年，5月20日，5點(diǎn)57分，星期日奇妙的結(jié)果： k 僅與模式串T有關(guān)！ KMP算法的推導(dǎo)過(guò)程：（見(jiàn)教材P81）請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：兩式聯(lián)立可得：T1Tk-1=Tj-(k-1) Tj-1S=a b a b c a b c a c b a bT=a b c a cik則T的k-11位S前i-1i-(k-1)位 即(4-2）式含義設(shè)目前打算與T的第k字符開(kāi)始比較(1)(2)T1Tk-1則T的j-1j-(k-1)位 S前i-1i-(k-1)位 即(4-3）式含義ikjS=a b a b c a b c a c b a bT=a b c a c剛才肯定是在S的i處和T的第j字符 處失配Tj-(

6、k-1) Tj-1 截取一段，但k有限制，1kjk是追求的新起點(diǎn)加速的前提：T首與Tj處有相同子串注意：j 為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn) k。式中僅剩一個(gè)未知數(shù)k，理論上已可解！7第7頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日根據(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

7、= next j （k 與j 顯然具有函數(shù)關(guān)系），則取T首與Tj處最大的相同子串新起點(diǎn) k怎么求？8第8頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日（1） next j 有何物理意義？nextj函數(shù)表征著模式T中最大相同前綴子串和后綴子串（真子串）的長(zhǎng)度。可見(jiàn)，模式中相似部分越多，則nextj函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。即：nextj越大，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越低（時(shí)間效率）。next j max k |1k1時(shí)，Nextj的值為：模式串的位置從1到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同

8、的子串的最大長(zhǎng)度加1。無(wú)首尾相同的子串時(shí)Nextj的值為1。 / Nextj=1表示從模式串頭部開(kāi)始進(jìn)行字符比較（2） next j 怎么計(jì)算？怎樣計(jì)算模式T所有可能的失配點(diǎn) j 所對(duì)應(yīng)的 nextj？10第10頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日從兩頭往中間比較 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8新匹配位k=nextj :next j 0 當(dāng)j1時(shí)max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情況01122312討論：j=1時(shí), next j 0；/屬于“j=1”情況;j=2時(shí),

9、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以此類(lèi)推，可得后續(xù)nextj值?？捎醚菔境绦蝌?yàn)證nextj與s無(wú)關(guān)，可以預(yù)先計(jì)算例：11第11頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日下一個(gè)要討論的問(wèn)題是：如何用遞推方式來(lái)求出最大相同子串的長(zhǎng)度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個(gè)問(wèn)題一旦解決，整個(gè)KMP算法就

10、可以掌握得很透徹了。void get_next(SString T, int &next ) / /求模式串T的next函數(shù)值并存入數(shù)組next 。i=1; next1=0; j=0;while(iT0 ) if(j= = 0|Ti= =Tj)+i; +j; nexti=j;else j=nextj; / get_next遞推法編程，參見(jiàn)教材P83程序12第12頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日求解nextj流程圖（遞推） i=1; j=0next1=0i1)f=n*fact(n-1); else f=1; return(f); 遞推法：fact=1; for ( i=1

11、; i=n; i+)fact*= i;例如：求f(n)=n!第14頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日第一步，先把模式T所有可能的失配點(diǎn)j 所對(duì)應(yīng)的nextj計(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 ( i=S0 & jT0) return i-T0; /子串結(jié)束，說(shuō)明匹配成功 else return0;/Index_KMP15第15頁(yè)，共21頁(yè)，2022

12、年，5月20日，5點(diǎn)57分，星期日前面定義的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 ba a a a ba a a a b討論： next j 是否完美無(wú)缺？先用演示程序驗(yàn)證似乎慢了一點(diǎn)？能否再提速？由此派生出next函數(shù)的改進(jìn)算法 T：a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4先計(jì)算nextj：此時(shí)效率不高的原因?yàn)椋鹤哟?位相同時(shí)，主串字符若與其中一個(gè)不相等，則不必再與其余3個(gè)比較。而實(shí)際上還在依次比較。a a a a b第16頁(yè)，共21頁(yè)，2022年，5月20日，5點(diǎn)57分，星期日void get_nextval(SString T, int &nextval )