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

4.5.3模式匹配１.模式匹配的概念設(shè)有給定的兩個(gè)串T和P，則在T中尋找等于P的子串的過程，稱為模式匹配，T稱為正文(text)，P稱為模式(pattern)。通常T長(zhǎng)度遠(yuǎn)遠(yuǎn)大于P的長(zhǎng)度，若在T中找到等于P的子串，則匹配成功；否則，匹配失敗。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第1頁(yè)。2．簡(jiǎn)單的模式匹配算法算法思想如下：對(duì)于i=0,1,…,n-m，依次執(zhí)行下列匹配：用p[0],p[1],…,p[m-1]依次與t[i],t[i+1],…,t[i+m-1]比較，若均對(duì)應(yīng)相等，則匹配成功，整個(gè)算法結(jié)束；若存在某個(gè)k(0≤k≤m-1)，使得p[k]≠t[i+k]，則立即結(jié)束這輪比較，將模式P向右移動(dòng)一位，再執(zhí)行下一個(gè)i的新一輪匹配。如執(zhí)行了n-m+1輪，即i從0到n-m的所有情況，在T中都沒有找到P的子串，則匹配失敗。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第2頁(yè)。#defineMAXN100#defineMAXM50chart[MAXN],p[MAXM];intsimple_match(t,p,n,m)chart[],p[];intn,m;{inti,j,k;for(i=0;i<=n-m;i++){for(j=0;k=i;j<m&&t[k]==p[j];k++,j++)if(j==m)return(i);}return(-1);}

簡(jiǎn)單模式匹配算法，在最壞的情況下，比較的總次數(shù)為：m(n-m+1)，則時(shí)間復(fù)雜度為：O(mn)。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第3頁(yè)。3．模式匹配的KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt三個(gè)人提出來的。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第4頁(yè)。Kunth-Morris-Pratt算法舉例：T：abcabcaabcabcabcd……P：abcabc

d(abc)a

bcd(a)bcabcdabcabc

d

(abc)abcd

數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串?dāng)?shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第5頁(yè)。KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)算法t[0]…t[i-j]t[i-j+1]…t[i-k]t[i-k+1]…t[i-1]t[i]

t[i+1]…

‖‖‖‖‖‖

p[0]p[1]…p[j-k]p[j-k+1]…p[j-1]p[j]

p[j+1]…‖‖‖?

p[0]p[1]…p[k-1]p[k]

p[k+1]如果模式P的開頭k個(gè)字符(p[0],…,p[k-1])依次與p[j]的前面k個(gè)字符(p[j-k],…,p[j-1])相同，那么可以省去煩瑣的一輪輪的比較，還可省去模式的前k個(gè)字符的比較，只需從t[i]與p[k]開始依次繼續(xù)進(jìn)行比較。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串?dāng)?shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第6頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串

在執(zhí)行匹配過程中一旦出現(xiàn)ti≠pj處失配，我們必須在模式P中找出一段p0p1…pk-1=pj-kpj-k+1….pj-1，這個(gè)k我們稱pj的“失敗鏈接值”，我們發(fā)現(xiàn)在尋找模式P的各個(gè)字符的失敗鏈接值與正文T無關(guān)，只依賴模式本身。在進(jìn)行匹配前，預(yù)先為模式P的每一個(gè)符號(hào)設(shè)置好它的失敗鏈接值，一旦出現(xiàn)ti≠pj處失配。那么就取出pj失敗鏈接值k，而下次匹配直接將模式P的pk開始與正文失敗處ti繼續(xù)比較下去。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第7頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串計(jì)算失敗鏈接值數(shù)組元素（對(duì)應(yīng)模式的下標(biāo)j）j012345678910pabcabcabbacflink[j]-10001234501數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第8頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串失敗鏈接值的函數(shù)：#defineMAXN100#defineMAXM50chart[MAXN],p[MAXM];intflink[MAXN];voidfaillink(charp[],intflink[],intm){intj=1,k;flink[0]=-1;while(j<m){k=flink[j-1];while(k!=-1&&p[k]!=p[j-1])k=flink[k];flink[j]=k+1;j++;}}//時(shí)間復(fù)雜度分析為O(m)數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第9頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串KMP算法intkmp_match(t,p,flink,n,m)chart[],p[];Intflink[],n,m;{inti,j;i=0;j=0;while(i<n){while(j!=-1&&p[j]!=t[i])j=flink[j];If(j==m-1)return(i-m+1);i++;j++;}return(-1)}//時(shí)間復(fù)雜度分析為O(n)數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第10頁(yè)。數(shù)據(jù)結(jié)構(gòu)第4章數(shù)組和串第5節(jié)串4．模式匹配BM（Boyer-Moore）算法

BM算法與KMP算法差別在于：（1）在模式匹配時(shí)，不是自左向右進(jìn)行，而是自右向左進(jìn)行。（2）事先計(jì)算一個(gè)函數(shù)d(x)，包含下列信息：當(dāng)x不在模式P中，或出現(xiàn)在P的尾端，則d(x)取值為模式P的長(zhǎng)度。其余情況，d(x)取值等于字符x在模式P中最右端的字符x到尾端的距離。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第11頁(yè)。

給定的模式P=p0p1p2….pm-1，模式P長(zhǎng)度為m，則D(x)函數(shù)表示如下：

m若x不在P，或x=pm-1，但x≠pi(0≤i≤m-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。數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第12頁(yè)。BM算法的思想：假設(shè)在執(zhí)行正文T中自第i起，與模式P開始自右向左的匹配，一旦發(fā)現(xiàn)不匹配，則去執(zhí)行pm-1與ti+d(ti)開始的自右向左的匹配，相當(dāng)于把整個(gè)模P向右滑過d(ti)個(gè)一段距離。若模式P在與正文第i位起的匹配過程中，假如中間某個(gè)符號(hào)與正文的符號(hào)不匹配，而ti不在模式中或是模的尾端，那么滑過的距離是最大的，也就是模P的長(zhǎng)度m。

數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第13頁(yè)。d(x):6614正文：thene

l

seturn

fathereturnreturnreturnreturnreturnreturn數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第14頁(yè)。算法#defineMAXN1000#defineMAXM50chart[MAXN],p[MAXM];intn,m;intd[26];voiddx(charp[],intd[],intm)//建立d[26]數(shù)組{inti;for(i=0;i<26;i++)d[i]=m;for(i=0;i<m-1;i++)d[p[i]-‘a(chǎn)’]=m-i-1;//字符到尾端最短距離}數(shù)據(jù)結(jié)構(gòu)-數(shù)組和串的模式匹配全文共16頁(yè)，當(dāng)前為第15頁(yè)。intBM_patter(t,p,d,n,m)chart[],p[];intd[],n,m;{inti,j,k;i=m-1;//正文第一次起始位置

do{j=m-1;k=i;while(j>=0&&p[j]==t[k]){j--;