數(shù)據(jù)結(jié)構(gòu)——數(shù)組和串的模式匹配ppt課件

1、4.5.3 方式匹配方式匹配. 方式匹配的概念方式匹配的概念 設(shè)有給定的兩個(gè)串設(shè)有給定的兩個(gè)串T和和P，那么在，那么在T中尋覓中尋覓等于等于P的子串的過(guò)程，稱(chēng)為方式匹配，的子串的過(guò)程，稱(chēng)為方式匹配，T稱(chēng)為正稱(chēng)為正文文(text)，P稱(chēng)為方式稱(chēng)為方式(pattern)。 通常通常T長(zhǎng)度遠(yuǎn)遠(yuǎn)大于長(zhǎng)度遠(yuǎn)遠(yuǎn)大于P的長(zhǎng)度，假設(shè)在的長(zhǎng)度，假設(shè)在T中中找到等于找到等于P的子串，那么匹配勝利；否那么，匹的子串，那么匹配勝利；否那么，匹配失敗。配失敗。2簡(jiǎn)單的方式匹配算法簡(jiǎn)單的方式匹配算法 算法思想如下：對(duì)于算法思想如下：對(duì)于i=0, 1, , n-m，依次，依次執(zhí)行以下匹配：執(zhí)行以下匹配： 用用p0, p1,

2、 , pm-1依次與依次與ti, ti+1, , ti+m-1比較，假設(shè)均對(duì)應(yīng)相等，那比較，假設(shè)均對(duì)應(yīng)相等，那么匹配勝利，整個(gè)算法終了；假設(shè)存在某個(gè)么匹配勝利，整個(gè)算法終了；假設(shè)存在某個(gè)k(0k m-1)，使得，使得pk ti+k，那么立刻終了，那么立刻終了這輪比較，這輪比較， 將方式將方式P向右挪動(dòng)一位，再執(zhí)行下向右挪動(dòng)一位，再執(zhí)行下一個(gè)一個(gè)i的新一輪匹配。的新一輪匹配。 如執(zhí)行了如執(zhí)行了n-m+1輪，即輪，即i從從0到到n-m的一切情的一切情況，在況，在T中都沒(méi)有找到中都沒(méi)有找到P的子串，那么匹配失敗。的子串，那么匹配失敗。#define MAXN 100#define MAXM 50ch

3、ar tMAXN, pMAXM ;int simple_match ( t, p, n, m)char t , p ;int n , m ; int i , j , k ; for (i=0 ; i=n-m ; i+ ) for (j=0 ; k=i ; jm& tk = p j ; k+ , j+) if (j = m ) return (i ) ; return (-1 ) ; 簡(jiǎn)單方式匹配算法，在最壞的情況下，比較的總次數(shù)為：m(n-m+1) ，那么時(shí)間復(fù)雜度為：O(mn)。3方式匹配的方式匹配的KMP算法算法 由由D.E.Knuth，J.H.Morris和和V.R.Pratt三

4、三個(gè)人提出來(lái)的。個(gè)人提出來(lái)的。Kunth-Morris-Pratt算法舉例：T： a b c a b c a a b c a b c a b c dP： a b c a b c d (a b c)a b c d (a)b c a b c d a b c a b c d (a b c)a b c d 數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)算法t0 ti-j ti-j+1 ti-k ti-k+1 ti-1 ti ti+1 p0 p1 pj-k pj-k+1 pj-1 pj pj+1 ? p0 p1 pk-1 pk pk+

5、1假設(shè)方式P的開(kāi)頭k個(gè)字符(p0, ,pk-1)依次與pj的前面k個(gè)字符(pj-k, ,pj-1)一樣，那么可以省去煩瑣的一輪輪的比較，還可省去方式的前k個(gè)字符的比較，只需從ti與pk開(kāi)場(chǎng)依次繼續(xù)進(jìn)展比較。數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串?dāng)?shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串 在執(zhí)行匹配過(guò)程中一旦出現(xiàn)tipj處失配，我們必需在方式P中找出一段p0p1pk-1 = pj-kpj-k+1.pj-1，這個(gè)k我們稱(chēng)pj的“失敗鏈接值，我們發(fā)如今尋覓方式 P的各個(gè)字符的失敗鏈接值與正文T無(wú)關(guān)，只依賴(lài)方式本身。 在進(jìn)展匹配前，預(yù)先為方式P的每一個(gè)符號(hào)設(shè)置好它的失敗鏈接值，一旦出現(xiàn)ti

6、pj處失配。那么就取出pj失敗鏈接值k，而下次匹配直接將方式P的pk開(kāi)場(chǎng)與正文失敗處ti繼續(xù)比較下去。數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串計(jì)算失敗鏈接值數(shù)組元素對(duì)應(yīng)方式的下標(biāo) j 存在其他情況且時(shí)當(dāng).00|max0111110ppppppjkjkjkjkkjjflinkj012345678910pabcabcabbacflinkj -10001234501數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串失敗鏈接值的函數(shù)：#define MAXN 100#define MAXM 50char tMAXN, pMAXM ;int flinkMAXN;void faillink(char p

7、 , int flink , int m ) int j=1, k ; flink0 = -1 ; while (jm) k=flinkj-1 ; while( k!=-1&pk!=pj-1 ) k=flinkk ; flinkj=k+1 ; j+; / 時(shí)間復(fù)雜度分析為O(m) 數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串KMP算法算法int kmp_match( t ,p , flink , n, m ) char t , p ; Int flink , n , m ; int i , j ; i=0 ; j=0 ; while( in) while( j!= -1 &

8、pj!=ti ) j=flinkj ; If (j=m-1) return (i-m+1) ; i+ ; j+ ; return (-1) / 時(shí)間復(fù)雜度分析為時(shí)間復(fù)雜度分析為O(n)數(shù)據(jù)構(gòu)造 第 4 章 數(shù)組和串 第 5 節(jié) 串4方式匹配方式匹配BMBoyer-Moore算法算法 BM算法與算法與KMP算法差別在于：算法差別在于： 1在方式匹配時(shí)，不是自左向右進(jìn)展，在方式匹配時(shí)，不是自左向右進(jìn)展，而是自右向左進(jìn)展。而是自右向左進(jìn)展。 2事先計(jì)算一個(gè)函數(shù)事先計(jì)算一個(gè)函數(shù)d(x)，包含以下信，包含以下信息：息： 當(dāng)當(dāng)x不在方式不在方式P中，或出如今中，或出如今P的尾端，那的尾端，那么么d(x)取

9、值為方式取值為方式P的長(zhǎng)度。的長(zhǎng)度。 其他情況，其他情況，d(x)取值等于字符取值等于字符x在方式在方式P中中最右端的字符最右端的字符x到尾端的間隔。到尾端的間隔。 給定的方式P=p0p1p2.pm-1，方式P長(zhǎng)度為m，那么D(x)函數(shù)表示如下： m 假設(shè)x不在P，或x=pm-1，但xpi (0im-2)d(x)= m-i-1 其他情況，這里i=max例P=doctor，由d(x)函數(shù)求出，d(r)=6，d(o)=1，d(t)=2，d(c)=3，d(d)=5，其他不在模中的符號(hào)的值d(x)=6。2)-mi(0 x,pi|iBM算法的思想： 假設(shè)在執(zhí)行正文T中自第 i 起，與方式P開(kāi)場(chǎng)自右向左的

10、匹配，一旦發(fā)現(xiàn)不匹配，那么去執(zhí)行pm-1與ti+d(ti)開(kāi)場(chǎng)的自右向左的匹配，相當(dāng)于把整個(gè)模P向右滑過(guò)d(ti)個(gè)一段間隔。 假設(shè)方式P在與正文第 i 位起的匹配過(guò)程中，假設(shè)中間某個(gè)符號(hào)與正文的符號(hào)不匹配，而 ti 不在方式中或是模的尾端，那么滑過(guò)的間隔是最大的，也就是模P的長(zhǎng)度m。 d(x): 6 6 1 4 正文：t h e n e l s e t u r n f a t h e r e t u r n r e t u r n r e t u r n r e t u r n r e t u r n r e t u r n算法算法#define MAXN 1000#define MAXM 50char tMAXN , pMAXM ;int n , m ;int d26 ;void dx(char p , int d , int m) / 建立建