1 / 25
文档名称:

KMP字符串模式匹配详解.doc

格式:doc   大小:234KB   页数:25页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

KMP字符串模式匹配详解.doc

上传人:小点 2019/3/22 文件大小:234 KB

下载得到文件列表

KMP字符串模式匹配详解.doc

相关文档

文档介绍

文档介绍:膄KMP字符串模式匹配详解收藏螂个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了,确实说得很“详细”,耐心地把它看完肯定会有所收获的~~,另外有关模式函数值next[i]确实有很多版本啊,在另外一些面向对象的算法描述书中也有失效函数f(j)的说法,其实是一个意思,即next[j]=f(j-1)+1,不过还是next[j]这种表示法好理解啊:芇KMP字符串模式匹配详解薆KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。:莇intIndex_BF(charS[],charT[],intpos)羇{莄/*若串S中从第pos(S的下标0≤pos<StrLength(S))个字符莀起存在和串T相同的子串,则称匹配成功,返回第一个蒇这样的子串在串S中的下标,否则返回-1*/肄inti=pos,j=0;袁while(S[i+j]!='\0'&&T[j]!='\0')腿if(S[i+j]==T[j])薇j++;//继续比较后一字符蒄else薃{膁i++;j=0;//重新开始新的一轮匹配蚇}袅if(T[j]=='\0')羁returni;//匹配成功返回下标羀else蚇return-1;//串S中(第pos个字符起)不存在和串T相同的子串芆}//Index_BF此算法的思想是直截了当的:将主串S中某个位置i起始的子串和模式串T相比较。即从j=0起比较S[i+j]与T[j],若相等,则在主串S中存在以i为起始位置匹配成功的可能性,继续往后比较(j逐步增1),直至与T串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始进行下一轮的"匹配",即将串T向后滑动一位,即i增1,而j退回至0,重新开始新一轮的匹配。螃例如:在串S=”abcabcabdabba”中查找T=”abcabd”(我们可以假设从下标0开始):先是比较S[0]和T[0]是否相等,然后比较S[1]和T[1]是否相等…我们发现一直比较到S[5]和T[5]才不等。如图:虿螆蚇当这样一个失配发生时,T下标必须回溯到开始,S下标回溯的长度与T相同,然后S下标增1,然后再次比较。如图:膁这次立刻发生了失配,T下标又回溯到开始,S下标增1,然后再次比较。如图:螂袆这次立刻发生了失配,T下标又回溯到开始,S下标增1,然后再次比较。如图:袄袃又一次发生了失配,所以T下标又回溯到开始,S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图:,在S=”abcabcabdabba”中查找T=”abcabd”,如果使用KMP匹配算法,当第一次搜索到S[5]和T[5]不等后,S下标不是回溯到1,T下标也不是回溯到开始,而是根据T中T[5]==’d’的模式函数值(next[5]=2,为什么?后面讲),直接比较S[5]和T[2]是否相等,因为相等,S和T的下标同时增加;因为又相等,S和T的下标又同时增加。。。最终在S中找到了T。如图:芅蚅KMP匹配算法和简单匹配算法效率比较,一个极端的例子是:芀在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”,简单匹配算法每次都是比较到T的结尾,发现字符不同,然后T的下标回溯到开始,S的下标也要回溯相同长度后增1,继续比较。如果使用KMP匹配算法,,简单匹配算法的时间复杂度可降为O(m+n),因此在多数的实际应用场合下被应用。蚆KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么T[5]==’d’的模式函数值等于2(next[5]=2),其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同,且T[5]==’d’不等于开始的两个字符之后的第三个字符(T[2]=’c’).如图:肃聿也就是说,如果开始的两个字符之后的第三个字符也为’d’,那么,尽管T[5]==’d’的前面有2个字符和开始的两个字符相同,T[5]==’d’的模式函数值也不为2,而是为0。膆前面我说:在S=”abcabcabdabba”中查找T=”abcabd”,如果使用KMP匹配算法,当第一次搜索到S[5]和T[5]不等后,S下标不是回溯到1,T下标也不是回溯到开始,而是根据T中T[5]==’d’的模式函数值,直接比较S[5]和T[2]是否相等。。。为什么可以这样?肇刚才我又说:“(next[5]=2),其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同”。请看图:因为,S[4]==T[4],S[3]==T[3],根