数据结构串B.ppt

* * * * * * * * * * * * * * * * 算法目的：确定主串中所含子串第一次出现的位置（定位） 4.3 串的模式匹配算法 BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法 算法种类： 带回溯，速度慢 避免回溯，匹配速度快， 是全课程的亮点之一 定位问题称为串的模式匹配，典型函数为Index(S,T,pos) * BF算法的实现 例1： S=‘ababcabcacbab’，T=‘abcac’，pos=1， 求：串T在串S中第pos个字符之后的位置。 BF算法设计思想： 将主串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0。 例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。 i = i –j +2; j = 1; * BF算法的实现 * 求子串位置的定位函数Index(S, T, pos) 的BF算法： Int Index_BP(SString S, SString T, int pos) //见教材P79 { //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.其中，T非空，1≤pos≤StrLength(S) i=pos; j=1; while ( i=S[0] j=T[0] ) { //如果i,j二指针在正常长度范围， if (S[i] = = T[j] ) {++i, ++j; } //则继续比较后续字符 else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配 } if(jT[0]) return i-T[0]; //T子串指针j正常到尾，说明匹配成功， else return 0; //否则属于iS[0]情况，i先到尾就不正常 } //Index_BP i-j=回到起始点之前， i-j＋1=回到首字符， i-j＋2=定位到第二个字符 BF算法的实现 BF算法的时间复杂度 主串长n； 子串长m。可能匹配成功的位置（1 ~ n-m+1)。 ①最好的情况下: 第i个位置匹配成功，前i-1个位置每个位置只比较了一次，第i个位置比较了（i-1+m）次，平均比较次数： ②最坏的情况下: 第i个位置匹配成功，但每个i-1位置都比较了m次，总共比较了(i*m)次，平均比较次数： 设nm，最坏情况下的平均时间复杂度为O(n*m)。 最好情况下算法的平均时间复杂度O(n+m)。 分析算法的思想： 从主串S的第pos个字符起和模式的第一个字符比较，若相等，继续比较后续字符；否则, 从主串的下一个字符起再重新和模式的字符比较。以此类推，直到模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数返回T首字符在S中的位置；否则匹配不成功。 问题：当主串与模式串存在多次部分匹配时，就显得效率低下。如0、1串在T=“00001”, S=“0000000000001”时，每次都有四次的多余比较，而0、1串又是普遍存在的。 模式匹配的改进算法-KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。 因t1≠t2,s2=t2,必有s2≠t1,又因t1=t3,s3=t3,所以必有s3=t1。因此,第二次匹配可直接从i=4, j=2开始。 * 尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。 例： ① KMP算法设计思想： (参见教材P80-84） S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ Index_kmp的返回值应为i=6 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ② 模式应该向右滑多远才是高效率的? i i i k k a