数据结构第09讲_串的模式匹配与串的应用_CVIP免费

第4章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.3.1求子串位置的定位函数4.3.2模式匹配的一种改进算法4.4串操作应用举例4.3串的模式匹配算法4.3.1求子串位置的定位函数又称模式匹配或串匹配，应用非常广泛。在串匹配中，假设S为目标串，P为模式串：S=‘s1s2...sn’P=‘p1p2…pm’串的匹配实际上是根据1≤i≤n-m+1依次将S的子串S’[i..i+m-1]和P[1..m]进行比较，若S’[i..i+m-1]=P[1..m]，则称从位置i开始的匹配成功；反之，匹配失败。上述的位置i又称为位移，当S’[i..i+m-1]=P[1..m]时，i称有效位移；当S’[i..i+m-1]≠P[1..m]时，i称无效位移。这样，串匹配问题可简化为是找出某给定模式串P在给定目标串S中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。基本思想：用一个循环来依次检查n-m+1个合法的位移i(1≤i≤n-m+1)是否为有效位移。算法段：for(i=1;i<=n-m+1;i++)if(S[i..i+m-1]=P[1..m])returni;例：设pos=1；模式串T=‘abcac’例：模式匹配的算法intIndex(SStrings,SStringp,intpos){j=1;i=pos;while(i<=s[0]&&j<=p[0]){if(s[i]==p[j]){i++;j++;}//继续比较后续字符else{i=i-j+2;j=1;}//指针回溯到下一首位，重新开始匹配}if(j>p[0])returni-p[0];//匹配成功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前若干字符相匹配的部分p1～pj-1第一种情况是：模式串中不存在相等真子串的情况，即p1～pj-1中不存在前k（1