数据结构第09讲-串的模式匹配与串的应用-Cppt课件

第4章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.3.1求子串位置的定位函数4.3.2模式匹配的一种改进算法4.4串操作应用举例,4.3串的模式匹配算法4.3.1求子串位置的定位函数又称模式匹配或串匹配，应用非常广泛。在串匹配中，假设S为目标串，P为模式串：S=s1s2.snP=p1p2pm串的匹配实际上是根据1in-m+1依次将S的子串Si.i+m-1和P1.m进行比较，若Si.i+m-1=P1.m，则称从位置i开始的匹配成功；反之，匹配失败。,上述的位置i又称为位移，当Si.i+m-1=P1.m时，i称有效位移；当Si.i+m-1P1.m时，i称无效位移。这样，串匹配问题可简化为是找出某给定模式串P在给定目标串S中首次出现的有效位移。,串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。基本思想：用一个循环来依次检查n-m+1个合法的位移i(1in-m+1)是否为有效位移。,算法段：for(i=1;i=n-m+1;i+)if(Si.i+m-1=P1.m)returni;,例：设pos=1；模式串T=abcac,例：模式匹配的算法intIndex(SStrings,SStringp,intpos)j=1;i=pos;while(ip0)returni-p0;/匹配成功elsereturn0;/Index,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,算法简单并易于实现，但在某些情况下时间效率不高，主要的原因是主串下标i在若干个字符序列比较相等后只要有一个字符比较不相等时便需要把下标i的值回退。算法的最坏情况是：当模式串p的前m-1个字符序列与主串s的相应字符序列比较总是相等，但模式串p的第m个字符与主串的相应字符比较总是不等。每次比较m个字符，比较n-m+1次，共比较m*(n-m+1)次，时间复杂度为O(n*m)。,4.3.2模式匹配算法的改进算法(KMP算法)1.匹配分析KMP算法的特点主要是消除了上述算法的主串下标i在若干次字符序列比较相等后只要有一个字符比较不相等便把下标i的值回退的缺点。分析上述算法可以发现，算法中的主串下标i值的回退并非一定必要。我们从2种情况来分析：,对于p中已与s前若干字符相匹配的部分p1pj-1第一种情况是：模式串中不存在相等真子串的情况，即p1pj-1中不存在前k（1kj-1）个字符等于后k个字符的情况。例：主串s=cddcde，模式串p=cde的模式匹配过程。当s1=p1，s2=p2，s3p3时，由于p1pj-1=cd，k=2,情况成立,即p2p1，所以定有s2p1，接下来可直接比较s3和p1。,第二种情况是：模式串中存在相等真子串的情况，即p1pj-1存在前k（1kj-1）个字符等于后k个字符的情况。例：主串s=aaabaaad，模式串p=aaad的模式匹配过程。当s1=p1，s2=p2，s3=p3，s4p4时，有p1=p3，还有p1p2=p2p3，取最大的相等子串p1p2=p2p3，有k=3，由于s2s3=p2p3,此时必然有s2s3=p1p2,显然，接下来可直接比较s4和p3。,总结以上2种情况可以发现：一旦有比较不相等时，主串s的下标不必回退，主串的si可直接和模式串的pk(1kj-1）比较，k的确定与主串s并无关系，k的确定只与模式串p本身的构成有关，即从模式串本身就可求出k的值。,利用已经部分匹配的结果而加快模式串的滑动速度，而且主串S的指针i不必回溯！可提速到O(n+m)！例：,S=ababcabcacbab,P=abcac,S=ababcabcacbab,P=abcac,S=ababcabcacbab,P=abcac,Index_kmp的返回值应为i=6,需要讨论两个问题：如何“记忆”部分匹配结果？如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k。,aba,abc,KMP算法设计思想,抓住部分匹配结果的两个特征：,两式联立可得：P1Pk-1=Pj-(k-1)Pj-1注意：j为当前已知的失配位置，我们的目标是计算新起点k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前i-1i-(k-1)位P的j-1j-(k-1)位即(4-3）式含义,则P的k-11位S前i-1i-(k-1)位即(4-2）式含义,刚才肯定是在S的i处和T的第j字符处失配,设目前应与T的第k字符开始比较,从模式串本身求出k的值当主串的si和模式串的pj比较不等时，由于满足关系式p1p2pk-1=pj-k+1pj-k+2pj-1则要确定与主串si比较的子串pk的k值，只需求出模式串p中的每个字符的nextj函数即可。,2.next函数令nextj=k,则表示主串和子串第j个元素失配时，应与第pk个字符比较。0当j=1时nextj=Maxk|1kyTHENz:=x;ELSEz:=y;RETURN(z);END;,该程序输入内存后放到一个堆中，如下图所示。其中为换行符。,页表,行表,本章小结,1.理解串的逻辑结构定义、物理存储结构表示；2.掌握串的基本操作算法，注意不同存储结构下，串的操作算法也有所不同；能熟练地上机编程，并能熟练进行串的基本运算；3.理解并掌握串的模式匹配算法，特别是KMP算法；能够计算模式串的next函数。,练1：串是由字符组成的序列，一般记为。,练2：现有以下4个字符串：a=BEI，b=JING，c=BEIJING，d=BEIJING，问：他们各自的长度？a是哪个串的子串？在主串中的位置是多少？,a=3，b=4，c=7，d=8,a是a、c和d的子串，在a、c和d中的位置都是1,0个或多个,S=a1a2an,练4：令模式串s=aaabt=abcabaau=abcaabbabcabaacbacba分别求出他们的next函数值。,练3：空串和空格串有无区别？答：有。空串(NullString)是指长度为零的串；而空格串(BlankString)，是指包含一个或多个空白字符(空格键)的字符串。,练5：从串S中删除所有和串T相同的子串。此题的操作等同于“以空串置换串S中所有和串T相同的子串。”,显然，算法的目标是构造如上所画的一个新串。,StringDelete(String/Delete,练6：顺序串上的插入insert(&S,i,T)要将T插入到S中第i个位置，则S串中第i个位置开始，一直到最后的字符，每个都要向后移动若干位，移动的位数为T串长度。具体实现如图。,voidInsert(SString/表长度增加,设s串长n,T串长m,该算法时间复杂度为o(n+m)。,练7：链串上的插入in