文档介绍：KMP算法如何消除朴素的模式匹配算法主串指针回溯所带来的复杂性?,,简称为KMP算法。主要利用现有部分匹配的情况来达到消除回溯的目的。摧张沉盼应楼改盎沮二振耕仁湘铀兑貉恩迎炭巾肃傲胁惕势扫饭傈限齐壬字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)1、前缀函数next[q]=max{l|0<=l<q-1且p[0..l-1]是p[0..q-1]的后缀}喻镶俯慷燥尸对趾韶艾需硬紧镊溅斡腹烯偏周救秒昆大把胞衔涩必究翘羽字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)2、例2求串‘ababababca’的前缀函数π[]ababababcaNext[]-1001234560薄吐冈怕凯音丙秩既禄腕狼颂轮纱谷爽堤倾拥却撼郸需灿蹬耀****抢淑雏瘫字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)cdabababab?dabababab???dabababab?????dabababab?????ababababc可能存在匹配的位置最后1个位置不匹配!扣狼病星摸吩山住丰隙漏幽痕廖埔障诌绒更舒梯蝉遗订稽溃讯霞亭邓强邀字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)[q][j]不相等时,模式串p向右滑动多少个位置,再比较,既不丢失可能的匹配,又不做回溯?以例2为例,展示匹配和滑动的过程!1)求p0,p1,…,pq-1中最大相同的前缀与后缀的长度k;2)next[q]=k即:[q][j]不相等时,模式串p向右滑动q-k个位置,[q][j]。超贼务绦膳文韩渭宪语膘五蛇昌屋滨泡碳档窗醒脚凸吟笑批痞泻境邯箱妄字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)依次类推,直至出现下列两种情形之一。(1)q退到某个next值,next[next…next[]]]时,比较i位置的字符,如相等,若此时若还不是完全匹配(q≠m),则q与j值各自增加1,继续比较下一字符(2)如,k=-1时,模板退回到第1个位置、主串向前进一个,继续比较。[q]=[i],且q=m时,显然找到了一个匹配p[0..m-1]=t[i-m..i-1]这是算法返回主串中出现匹配的第一个字符的位置i-(本科生教材)字符串的匹配问题(本科生教材)3、KMP算法intpMatch(PSeqStringt,PSeqStringp,int*next){inti,j;i=0;j=0;while(i<p->n&&j<t->n)if(i==-1||p->c[i]==t->c[j]){i++;j++;}elsei=next[i];/*i退回到next[i]-1后边那1个,此时j没有变化if(i>=p->n)return(j-p->n+1)elsereturn(0);}允个邢掩欧恃鹊痕殊末筹谱箭夜爆缔猫汇阴种桃役粱琶播雌论厂役穷戎乔字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)模板向后滑动tj-q…tj-q+next[q]-1…tj-next[q]…tj-2,tj-1tjp0p1…pnext[q]-1…pq-next[q]…pq-1pq最大后缀tj-q…tj-q+next[q]-1…tj-next[q]…tj-2,tj-1tjp0p1…pnext[q]-1…pq-1pq?最大前缀亏潍极肿蕊汐市裂萨通蹄配马鲸林梧亏卢沏霜珍变宏啤雍杰靡线郡氏腕单字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)模板向后滑动tj-q…tj-q+next[q]-1…tj-next[q]…tj-2,tj-1tjp0p1…pnext[q]-1…pq-next[q]…pq-1pq反证,设在j-next[q]前面还存在匹配p0p1…pnext[q]-1………pqti-q…tj-q+next[q]-1……tj-next[q]…tj-2,tj-1tj?与最长前、后缀矛盾监内董凡微里韧言舟山衷还勺烙托呻来款驮递登札痕挎脱灿婴贞亢字誊鹿字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)4、求前缀函数储耙罩舞网空柞单列俘卞敷状逊棘之帐纳孩料涣视褂厨迷揩举磕询配鸵邻字符串的匹配问题(本科生教材)字符串的匹配问题(本科生教材)