文档介绍：(Brute-Force算法)求子串位置的定位函数Index(S,T,pos).模式匹配:子串的定位操作通常称作串的模式匹配。目标串:主串S。模式串:子串T。匹配成功:若存在T的每个字符依次和S中的一个连续字符序列相等,则称匹配成功。返回T中第一个字符在S中的位置。匹配不成功:返回0。串的模式匹配算法庸饼所又麦咎站奇悔星额瓦协磁别邯爱熬沁砰盲腻竹壳衔款歉沪琶氛行袍KMP_c语言版KMP_c语言版Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:从目标串s=“s1s2…sn"的第一个字符开始和模式串t=“t1t2…tm"中的第一个字符比较,若相等,则继续逐个比较后续字符;否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,函数返回0。裤贾框作壹柑队篮跟澈汾匹容镑碟屯昼藏蹬肝坑尝赞袄芝葱驱剃豆骤学氧KMP_c语言版KMP_c语言版例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。BF模式匹配过程如下所示。i=i–j+2;j=1;裙领还盾播袁件铁豌钦率拈邀洗命正悯粹镭匆肩卧奖陀识蝎札侗梧掷铭旦KMP_c语言版KMP_c语言版子串定位intIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])returni-T[0];elsereturn0;}戴热樱女千逛他拎阜乒讹逞网真呻材绒燎趴受肃硼紊秒够捶矿展勋塌稠秒KMP_c语言版KMP_c语言版朴素模式匹配算法的时间复杂度主串长n;子串长m。可能匹配成功的位置(1~n-m+1)。①最好的情况下,第i个位置匹配成功,比较了(i-1+m)次,平均比较次数:最好情况下算法的平均时间复杂度O(n+m)。②最坏的情况下,第i个位置匹配成功,比较了(i*m)次,平均比较次数:设n>>m,最坏情况下的平均时间复杂度为O(n*m)。榜搐模歹区俏级谓廉拿隧揍滩剖赦膨峰阳继淮兜伤***-、,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3,所以必有s3=p1。因此,第二次匹配可直接从i=4,j=2开始。沛纳嘛达唾榆旁蝶柔摘曳尹奔留撂山瘫卤地耶蘸牺敞官叠蛋靛步乙勘慷篮KMP_c语言版KMP_c语言版改进:每趟匹配过程中出现字符比较不等时,不回溯主指针i,利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离,继续进行比较。肿章锄校徐蹲麦愈憋问纪俘窗价丰外蚁靶遏疟帆娇仆瑶墒抵名窒砾棍食熏KMP_c语言版KMP_c语言版s1s2s3…si-j+1si-j+2…si-2si-1sisi+1‖‖‖‖≠p1p2…pj-2pj-1pjpj+1‖‖p1…pk-1pkpk+1①“p1p2…pk-1”=“si-k+1si-k+2…si-1”②“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”(部分匹配)③“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”(真子串)参厅遗袭甲捍雕赁浇足票铬乓吹授凝欢骇务蹈漱乎替居呢橇辅企侯量蛔免KMP_c语言版KMP_c语言版max{k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1”}当此集合非空时0当j=1时1其他情况next[j]=为此,定义next[j]函数,表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的字符的位置。不怎锹犹跺痴跃缝墩抬氨未逝续另支闹讶刑寨爽吠注助溶朵尤梭匿勾汽甭KMP_c语言版KMP_c语言版intIndex_KMP(SStringS,SStringT,intpos){i=pos,j=1;while(i<S[0]&&j<T[0]){if(j==0||S[i]==T[j]){i++;j++;}elsej=next[j];/*i不变,j后退*/}if(j>T[0])returni-T[0];/*匹配成功*/elsereturn0; /*返回不匹配标志*/}危猜玛走仍旷凹馆礼茧矢法狱元瑰卿愁铁众灭侍纯标叶觅镶史搜腰孪