数据结构-数组和串的模式匹配

4.5.3模式匹配１.模式匹配的概念设有给定的两个串T和P，则在T中寻找等于P的子串的过程，称为模式匹配，T称为正文(text)，P称为模式(pattern)。通常T长度远远大于P的长度，若在T中找到等于P的子串，则匹配成功；否则，匹配失败。2．简单的模式匹配算法算法思想如下：对于i=0,1,…,n-m，依次执行下列匹配：用p[0],p[1],…,p[m-1]依次与t[i],t[i+1],…,t[i+m-1]比较，若均对应相等，则匹配成功，整个算法结束；若存在某个k(0≤k≤m-1)，使得p[k]≠t[i+k]，则立即结束这轮比较，将模式P向右移动一位，再执行下一个i的新一轮匹配。如执行了n-m+1轮，即i从0到n-m的所有情况，在T中都没有找到P的子串，则匹配失败。#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);}

简单模式匹配算法，在最坏的情况下，比较的总次数为：m(n-m+1)，则时间复杂度为：O(mn)。3．模式匹配的KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt三个人提出来的。Kunth-Morris-Pratt算法举例：T：abcabcaabcabcabcd……P：abcabc

d(abc)a

bcd(a)bcabcdabcabc

d

(abc)abcd

数据结构第4章数组和串第5节串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个字符(p[0],…,p[k-1])依次与p[j]的前面k个字符(p[j-k],…,p[j-1])相同，那么可以省去烦琐的一轮轮的比较，还可省去模式的前k个字符的比较，只需从t[i]与p[k]开始依次继续进行比较。数据结构第4章数组和串第5节串数据结构第4章数组和串第5节串在执行匹配过程中一旦出现ti≠pj处失配，我们必须在模式P中找出一段p0p1…pk-1=pj-kpj-k+1….pj-1，这个k我们称pj的“失败链接值”，我们发现在寻找模式P的各个字符的失败链接值与正文T无关，只依赖模式本身。在进行匹配前，预先为模式P的每一个符号设置好它的失败链接值，一旦出现ti≠pj处失配。那么就取出pj失败链接值k，而下次匹配直接将模式P的pk开始与正文失败处ti继续比较下去。数据结构第4章数组和串第5节串计算失败链接值数组元素（对应模式的下标j）j012345678910pabcabcabbacflink[j]-10001234501数据结构第4章数组和串第5节串失败链接值的函数：#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++;}}//时间复杂度分析为O(m)数据结构第4章数组和串第5节串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)}//时间复杂度分析为O(n)数据结构第4章数组和串第5节串4．模式匹配BM（Boyer-Moore）算法BM算法与KMP算法差别在于：（1）在模式匹配时，不是自左向右进行，而是自右向左进行。（2）事先计算一个函数d(x)，包含下列信息：当x不在模式P中，或出现在P的尾端，则d(x)取值为模式P的长度。其余情况，d(x)取值等于字符x在模式P中最右端的字符x到尾端的距离。给定的模式P=p0p1p2….pm-1，模式P长度为m，则D(x)函数表示如下：

m若x不在P，或x=pm-1，但x≠pi(0≤i≤m-2)d(x)=m-i-1其余情况，这里i=max例P=”doctor”，由d(x)函数求出，d(‘r’)=6，d(‘o’)=1，d(‘t’)=2，d(‘c)=3，d(d’)=5，其他不在模中的符号的值d(x)=6。BM算法的思想：假设在执行正文T中自第i起，与模式P开始自右向左的匹配，一旦发现不匹配，则去执行pm-1与ti+d(ti)开始的自右向左的匹配，相当于把整个模P向右滑过d(ti)个一段距离。若模式P在与正文第i位起的匹配过程中，假如中间某个符号与正文的符号不匹配，而ti不在模式中或是模的尾端，那么滑过的距离是最大的，也就是模P的长度m。

d(x):6614正文：thene

l

seturn

fathereturnreturnreturnreturnreturnreturn算法#defineMAXN1000#defineMAXM50chart[MAXN],p[MAXM];intn,m;intd[26];voiddx(charp[],intd[],intm)//建立d[26]数组{inti;for(i=0;i<26;i++)d[i]=m;for(i=0;i<m-1;i++)d[p[i]-‘a’]=m-i-1;//字符到尾端最短距离}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--;