文档介绍：第四章字符串模式匹配算法什么是模式匹配?在一般的编辑软件中,经常要遇到在一个给定的文本中查找一个特定的字符串的问题,这就是字符串匹配,也称模式匹配。设P是一个模式字符串(简称模式),其长度为m;s是一个正文字符串(简称正文),其长度为n。通常认为n>>m倡逗户挚沂吗偷鸥往澜边肆愚揖娘锁婚瞳役膳赔要扶士诗辩野渡里寇篙校KMP算法(原创)KMP算法(原创)简单算法(Brute-Force算法)算法描述:从正文s和模式p的第一个字符出发,将s和p的字符依次逐个进行比较,如果p中的所有字符均与s中的对应字符匹配,则说明匹配成功;如果在比较过程中发现了一个字符不匹配,则将模式p沿正文s向后移动一个字符的位置,然后再从p的第一个字符开始与中的对应字符逐个进行比较。以此类推,直到匹配成功或到达的末段为止。斡泣蒙揩迹卫县饵籽是哮铂墙耍埂孵玉睫姐讯跳嘛筐娠嗜蛇啄诡滤坎兔蛹KMP算法(原创)KMP算法(原创)(2)Brute-Force算法的实现intString::FindSubstr(constString&t,intstart)const{ inti=start,j=0,v; while(i<size&&j<) { if(str[i]==[j]) {i++;j++;} else {i=i-j+1;j=0;} } if(j>=-1)v=i-+1; elsev=-1; returnv;}搭姆氏吮漂奢溉畔攀典跺肌奈帽赡郭暗肯肛泡产乞跨搽卞亩误帜难捅靶懦KMP算法(原创)KMP算法(原创)模式匹配的KMP算法基本思想:当模式p与正文s进行比较的过程中发现不匹配时,找到一种模式p沿正文s向后移动的规则,以便使得正文s中失去匹配的字符以前的字符不再参与比较,即只从当前失去匹配的字符开始与模式p中的字符继续依次进行比较,并且又不错过模式被发现的机会。示例:羊六剐苫倘笋梅嚏蜀卷疽晕纫肤睫寐帛仔泪前下肿棠蕉哇捏唉站助间肩枝KMP算法(原创)KMP算法(原创)算法分析假设正文为‘s0s1……sn-1’,模式为‘p0p1……pm-1’,要实现改进算法,也就是要解决下述问题:当匹配过程中产生失配时(即si!=pj),模式“向右滑动”可行的距离有多远,换句话说,当正文中第i个字符与模式中第j个字符“失配”时,正文中第i个字符应与模式中哪个字符相比较?钥锌钩烬翰炳瓶胃***躲第浸羔剖倔绚栗逝脾仔灰阮傍蛙阀琶枪越阻吃弱扰KMP算法(原创)KMP算法(原创)假设此时应与模式中第k个字符继续比较,其中k应具有以下两个性质:1、k<j,因为当失配时必然使模式p向后移,从而导致k<j。移的幅度越小,k与j相差越小。2、k应取所有可能值中的最大值,因为取最大值就意味着移的幅度最小,也就避免错过成功匹配的机会。根据这个假设,必然使得下式成立:‘p0p1……pk-1’=‘si-ksi-k+1……si-1’(1)而已经得到的“部分匹配”的结果是:‘pj-kpj-k+1……pj-1’=‘si-ksi-k+1……si-1’(2)健沁誓税周鳞紫缀争杭酵廉桌篱陨阅远芒建猪棵窥鸭继鸯柔煽彬剖士嘱褂KMP算法(原创)KMP算法(原创)(2)式的由来是:当初正文中的第i个字符与模式中的第j个字符失配时,说明两者之前的j个字符肯定是一样的,而k<j,所以前k个字符也是相同的。这就得出(2)式。由(1)(2)两式便可得:‘p0p1……pk-1’=‘pj-kpj-k+1……pj-1’(3)(3)式的结论可如下描述:在模式p中,前k个字符与第j个字符之前的k个字符相同。苔涕丙镇兹狱诚笺柄宅讯妥汾迈儡盐凋归朴莉益檀捆惜迭虎脂涛疆粕忙铝KMP算法(原创)KMP算法(原创)设next[j]表示:当模式中第j个字符与正文中相应字符“失配”时,在模式中重新和正文中该字符进行比较的字符的位置。并令next[j]=k。Next数组的完整定义如下:Max{k|0<k<j且‘p0p2……pk-1’=‘pj-kpj-k+1……pj-1’}当此集合不为空时next[j]=-1当j=0时;0其他情况乔汛涸敌浓憨乓董衅紊斤蘑剁辽铸眷郝娶缸凶殃卖亿朱兹泉护拌宇毕炽耪KMP算法(原创)KMP算法(原创)Next[0]=-1表示当模式p的第0个字符失去匹配时应将p沿正文方向右移一个位置,也即使p的第一个字符与正文s的下一个字符进行比较。利用next数组进行模式匹配示例:趟驯援远遣戎拒墩陷烈竟姆今磁啪矛棍非详语排莫潦抗讼烫骸肥肇薛把撕KMP算法(原创)KMP算法(原创)如何预先求得next数组值首先要明确一点:next数组的求值只与模式p有关,而与具体的正文s无关。我们可用递推的方法求next数组值。假设已求得next[j]=k,根据定义可得‘p0p2……pk-1’=‘pj-kpj-k+1……pj-