数据结构第09讲_串的模式匹配与串的应用ppt课件.ppt

《数据结构第09讲_串的模式匹配与串的应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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

2、..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;

3、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

4、个字符序列与主串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中不存在

5、前k（1

6、p3，有k=3，由于s2s3=p2p3,此时必然有s2s3=p1p2,显然，接下来可直接比较s4和p3。总结以上2种情况可以发现：一旦有比较不相等时，主串s的下标不必回退，主串的si可直接和模式串的pk(1

7、Index_kmp的返回值应为i=6需要讨论两个问题：①如何“记忆”部分匹配结果？②如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k。iiikkabaabcKMP算法设计思想抓住部分匹配结果的两个特征：两式联立可得：‘P1…Pk-1’=‘Pj-(k-1)…Pj-1’注意：j为当前已知的失配位置，我们的目标是计算新起点k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！则S前i-1～i-(k-1)位＝P的j-1～j-(k-1)位即(4-3）式含义S=‘ababcabcacbab’P=‘abcac’