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

《数据结构-数组和串的模式匹配》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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向右移动一位，再执行下

2、一个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

3、(mn)。3．模式匹配的KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt三个人提出来的。Kunth-Morris-Pratt算法举例：T：abcabcaabcabcabcd……P：abcabcd(abc)abcd(a)bcabcdabcabcd(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

4、[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的各个字符的失败链接值

5、与正文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(c

6、harp[],intflink[],intm){intj=1,k;flink[0]=-1;while(j

7、)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≤

8、i≤m-2)d(x)=m