从头到尾彻底理解KMP

所需积分/C币:38 2018-07-31 17:22:09 37.72MB PDF
收藏 收藏 3
举报

CSDN博主写的一遍KMP算法,图文并茂,经过作者多次改版,日臻完善,非常详细介绍了KMP的方方面面。非常实用,值得一读。
BBC ABCDAB AB CDABCDABDE ABCDABDI 6.至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了S[9]、P[5],但因为S[10跟P6]不匹配,所以文本串回溯到 S5],模式串回溯到P[o],从而让S⑤5跟P[0匹配。 BBC ABCDAB ABCDABCDABDE BCD△BD 而S[5肯定跟P0失配。为什么呢?因为在之前第4步匹配中,我们已经得知S[5=P[1]=B,而P]=A,即P[1]=P[],故S]必定不等于 P[],所以回溯过去必然会导致失配。那有没有一种算法,让不往回退,只需要移动即可呢 答案是肯定的。这种算法就是本文的主旨KMP算法,它利用之前已经部分匹配这个有效信息,保持不回溯,通过修改的位置,让模式串尽 量地移动到有效的位置。 3.KMP算法 31定义 Knuh- Morris-Prat字符串查找箅法,简称为“KMP算法",常用于在一个文本串S内查找一个模式串P的岀现位置,这个算法由 Donald knuth、 Vaughan Pratt.、J mesH. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。 下面先直接给出KMP的箅法流程(如果感到一点点不适,没关系,坚持下,稍后会有具体步骤及解释,越往后看越会柳暗花明③) ·假设现在文本串S匹配到i位置,模式串P匹配到j位置 如果=-1,或者当前字符匹配成功(即S==P]),都令++,+,继续匹配下一个字符; ·如果j!=-1,且当前字符匹配失败(即S町!=P),则令i不变,j=next。此举意味着失配时,模式串尸相对于文本串S向右移动了j-nextⅢ位。 換言之,当匹配失败时,模式串向右移动的位数为∶失配字符所在位置-失配字符对应的ηext值(nex数组的求解会在下文的3.3.3节中详细阐 述),即移动的实际位数为:jext[j,且此值大于等于1。 很快,你也会意识到next数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。例如如果next=k,代表之前的字符串中有最大长度 为k的相同前缀后缀。 此也意味着在某个字符失配时,该字符对应的ηext值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next囗的位置)。如果nex等于0或-1,则跳到 模式串的开头字符,若next=k且k>0,代表下次匹配跳到之前的某个字符,而不是跳到开头,且具体跳过了k个字符 转换成代码表示,则是: 1 int KmpSearch(char* s, chan* p) int i=0: nt int slo trlen(s)i int pLen= strlen(p) ile(i< sLen &&3< pLen //如=-1,或芹当前字四院成(即5[1]=P1),那空计+,+ 19 if (j H|s[i]==p[j]) 16 /②如)1=-1,且当前字符次败(5[11=P[11),则令t不交,j= nextel7 /next订为所对的?ext值 1 21 if (i= pLen)23 else return -; 26 继续拿之前的例子来说,当S[10眼P6匹配失败时,κMP不是跟暴力匹配那样简单的把模式串右移—位,而是执行第②条指令:如果」!=-1,且当前字符匹配失 败(即S!=P),则令i不变,j=nex町”,斷从6变到2(后面我们将求得P6],即字符D对应的next值为2),所以相当于模式串向右移动的位数为j-next〔j -next=6-2=4 BBC ABCDAB AB CDABCDABDE ABCDABDI 向右移动4位后,S[10]跟P[2继续匹配。为什么要向右移动4位呢,因为移动4位后,模式串中又有个"AB可以继续跟S[8]S[⑨对应着,从而不用让i回溯。相当于 在除去字符D的模式串子串中寻找相同的前缀和后缀,然后根据前缀后缀求出ηext数组,最后基于nex数组进行匹配(不关心nex数组是怎么求来的,只想看匹配 过程是咋样的,可直接跳到下文3.34节)。 BBC ABCDAE ABCDABCDABDE ABCDABD 32步骤 ·①寻找前缀后缀最长公共元素长度 对于P=pop1…-1pj,寻找模式串中长度最大且相等的前缀和后缀。如果存在pOp1…pk-1pk=p-kp」-k1.Pj-1p,那么在包含p的模式串中有最 大长度为k+1的相同前缀后缀。举个例子,如果给定的模式串为"abab",那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示: 模式串 a b b 最大前缀后缀公共 0 0 2 元素长度 比如对于字符串aba来说,它有长度为1的相同前缀后缀a;而对于字符串abab来说,它有长度为2的相同前缀后缀ab(相同前缀后缀的长 度为k+1,k+1=2)。 ②求nex数组 ηext数组考虑的是除当前字符外的最长相同前缀后缀,所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第①步骤 中求得的值整体右移-位,然后初值赋为-1,如下表格所示: 模式串 b nex数组 0 0 比如对于aba来说,第3个字符a之前的字符串ab中有长度为0的相同前缀后缀,所以第3个字符a对应的next值为0;而对于abab来说,第4 个字符b之前的字符串aba中有长度为1的相同前缀后缀a,所以第4个字符b对应的nex值为1(相同前缀后缀的长度为k,k=1) ③根据next数组进行匹配 匹配失配,j=next,模式串向右移动的位数为:j-nexi。换言之,当模式串的后缀-kpk+1,…,pj-1跟文本串si-ksik+1.…,-1匹配成功,但跟 匹配失败时,因为 nextEl]=k,相当于在不包含P的模式串中有最大长度为k的相同前缀后级,即pOp1…pk-1=pjkp-k+1.pj-1,故令j=next,从 而让模式串右秘-nex切位,使得模式串的前缀p0p1,…pk<-1对应着文本串s-ksi-k+1,…,s-1,而后让pk跟si继续匹配。如下图所示 S, i-1 PP…PP…P地2…P J-next] 长度为k的最长相同前缓后缓 ↓next订 综上,KMP的next数组相当于告诉我们:当模式串中的某个字符跟文本串中的某个字符匹配失配时,模式串下一步应该跳到哪个位置。如模式串中在处的字符 跟文本串在i处的字符匹配失配时,下一步用next处的字符继续跟文本串i处的字符匹配,相当于模式串向右移动j-ηex切位。 接下来,分别具体解释上述3个步骤。 33解释 3.31寻找最长前缀后缀 如果给定的模式串是:" ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示 模式串的各个子串 前缀 后缀 最大公共元素长度 AB A B 0 ABC AB C BC ABCD AAB. ABC D. CD.BCD 0 CDA A ABABCABCD A DA CDA BCDA ABCDAB A.ABABCABCD ABCDA BAB, DAB, CDAB. BCDAB 2 AABABC.ABCD ABCDA D.BDABD DABD CDABD ABCDABD 0 ABCDAB BCDABD 也就是说,原模式串子串对应的各个前缀后缀的公共元素的最大长度表为(下简称《最大长度表》) 字符 最大前缀后缀 公共元素长 332基于《最大长度表》匹配 因为模式串中首尾可能会有重复的字符,故可得出下述结论 失配时,模式串向右移动的位数为:已匹配字符数-失配字符的上一位字符所对应的最大长度值 下面,咱们就结合之前的《最大长度表》和上述结论,进行字符串的匹配。如果给定文本串“ BBC ABCDAB ABCDABCDABDE”,和模式串" ABCDABD”,现在要 拿模式串去眼文本串匹配,如下图所示 BBC ABCDAB ABCDABCDABDE ABCDABD ·1.因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配,所以不必考虑结论,直接将模式串不断的右移一位即可,直到模弌串中的字符A 跟文本串的第5个字符A匹配成功 BBC JABCDAB ABCDABCDABDE ABCDABD ·2.继续往后匹配,当模式串最后一个字符D跟文本串匹配时失配,显而易见,模式串需要向右移动。但向右移动多少位呢?因为此时已经匹配的字符数为6个 ABCDAB),然后根据《最大长度表》可得失配字符D的上—位字符B对应的长度值为2,所以根据之前的结论,可知需要向右移动6-2=4位。 BBC ABCDAB ABCDABCDABDE ABCDABDI ·3.模式串向右移动4位后,发现C处再度失配,因为此时已经匹配了2个字符(AB),且上一位字符B对应的最大长度值为0,所以向右移动:2-0=2位。 BBC ABCDAR ABCDABCDABDE AECDABD 4.A与空格失配,向右移动1位 BBC ABCDAE ABCDABCDABDE ABCDABD ·5.继续比较,发现D与C失配,故向右移动的位数为:已匹配的字符数6减去上一位字符巳对应的最大长度2,即向右移动6-2=4位。 BBC ABCDAB ABCDAECPABDE ABCDABDI ·6.经历第5步后,发现匹配成功,过程结束 BBC ABCDAB ABCDABCDA把 ABCDAEDI 通过上述匹配过程可以看岀,问颋的关键就是寻找模式串中最大长度的相同前缀和后缀,找到了模式串中每个字符之前的前绥和后缀公共部分的最大长度后,便 可基于此匹配。而这个最大长度便正是next数组要表达的含义 333根据《最大长度表》求next数组 由上文,我们已经知道,字符串 ABCDABD各个前缀后缀的最大公共元素长度分别为: 模式串 A C D B 前后缀最大公|0 B0 0 共元素长度 而且,根据这个表可以得出下述结论 失配时,模式串向右移动的位数为:已匹配字符数-失配字符的上一位字符所对应的最大长度值 上文利用这个表和结论进行匹配时,我们发现,当匹配到一个字符失配时,其实没必要考虑当前失配的字符,更何况我们每次失配时,都是看的失配字符的上 位字符对应的最大长度值。如此,便引出了next数组。 给定字符串 ABCDABD”,可求得它的next数组如下 模式串 A D D next 0 0 0 2 把next数组跟之前求得的最大长度表对比后,不难发现,next数组相当于“最大长度值”整体向右移动一位,然后初始值赋为-1。意识到了 这一点,你会惊呼原来next数组的求解竟然如此简单∶就是找最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1(当然,你也可以直 接计算某个字符对应的nex值,就是看这个字符之前的字符串中有多大长度的相同前缀后缀) 换言之,对于给定的模式串: ABCDABD,它的最大长度表及next数组分别如下 模式串 A C D A D 最大长度值0 B00 B21 0 next数组 0 0 0 根据最大长度表求出了next数组后,从而有 失配时,模式串向右移动的位数为:失配字符所在位置-失配字符对应的next值 而后,你会发现,无论是基于《最大长度表》的匹配,还是基于next数组的匹配,两者得出来的向右移动的位数是一样的。为什么呢?因 为 ·根据《最大长度表》,失配时,模式串向右移动的位数=已经匹配的字符数-失配字符的上一位字符的最大长度值 而根据《neκt数组》,失配时模式串向右移动的位数=失配字符的位置-失配字符对应的next值 其中,从0开始计数时,失配字符的位置≡已经匹配的字符数(失配字符不计数),而失配字符对应的ηext值≡失配字符的上一位字符的最大长度值 两相比较,结果必然完全一致。 所以,你可以把《最大长度表》看做是next数组的雏形,甚至就把它当做next数组也是可以的,区别不过是怎么用的问题。 334通过代码递推计算next数组 接下来,咱们来写代码求下next数组。 基于之前的理解,可知计算next数组的方法可以采用递推: 1.如果对于值k,已有p0p1,…,pk-1=pjkp-k+1,…,pj-1,相当于 nextp]=k 此意味着什么呢?究其本质,next=k代表p]之前的模式串子串中,有长度为k的相同前缀和后缀。有了这个next数组,在KMP匹配中,当模式串中 j处的字符失配时,下一步用nex处的字符继续跟文本串匹配,相当于模式串向右移动-nex切位 举个例子,如下图,根据模式串“ ABCDABD"的next数组可知失配位置的字符D对应的next值为2,代表字符D前有长度为2的相同前缀 和后缀(这个相同的前缀后缀即为AB"),失配后,模式串需要向右移动-next们=6-2=4位 BBC ABCDAB ABCDABCDABDE AB CDABDI 向右移动4位后,模式串中的字符C继续跟文本串匹配。 BBC ABCDAE ABCDABCDABDE ABCDABD 2.下面的问题是:已知next0,…,j,如何求出next+1呢 对于P的前+1个序列字符 ·若pKk]==p,则next+1]=next]+1=k+1 ·若pk]≠p,如果此时 pl nextk]]=p],则nexj+1]= nextk+1,否则继续递归前缀索引k=nex],而后重复此过程。相当于在字符p+1之前不存 在长度为k+1的前缀"pop1,……,pk-1pk"跟后缀pkp-k+1,…,pj-1p"相等,那么是否可能存在另一个值t+1<k+1,使得长度更小的前缀"p0p1,,pt1pt"等 于长度更小的后缀“ pj-t pj-t+1,…,p-1p”呢?如果存在,那么这个t1便是 next[j+1的值,此相当于利用已经求得的next数组(next,…,k,…,)进行P串 前缓跟P串后缀的匹配 般的文章或教材可能就此一笔带过,但大部分的初学者可能还是不能很好的理解上述求解next数组的原理,故接下来,我再来着重说明下。 如下图所示,假定给定模式串 ABCDABCE,且已知next]=k(相当于"p0pk-1"="pi-kpj-1”=AB,可以看出k为2),现要求next+1等于多少?因为pk=pj= C,所以nex+们=nex+1=k+1(可以看出nex+1]=3)。代表字符E前的模式串中,有长度k+1的相同前缀后缀 模式串A 前后缀 相同长0 0 0 1 0 度 next 值 索引p0 pp Pi-k .但如果呢?说明p0pk-1pk”≠k-1可。换言之,当pk!=p后,字符E前有多大长度的相同前缀后缀呢?很明显,因为C不同于D,所以ABC跟A 不相同,即字符前的模式申没有长度为k+1的相同前缀后缀,也就不能再简单的令:neⅫ+1]=nex+1。所以,咱们只能去寻找长度更短一点的相同前缀 后缀 模式串A 前后缀 相同长 0 度 next值-1 0 0 索引 po pe p. pe. p. B p. 结合上图来讲,若能在前缀”p0pk-1pk“中不断的递归前缀索引k=nex↑[k],找到一个字符pk也为D,代表p=pj,且满足p0pk'-1pk'=pj-k'pj-1 pj,则最大相同的前缀后缀长度为k'*1,从而next+们=k'+1= next [k]+1。否则前缀中没有D,则代表没有相同的前缀后缀,next+们=0。 那为何递归前缀索引k=ηex],就能找到长度更短的相冋前缀后缀呢?这又归根到nex数组的含义。我们拿前缀popk-1pk去跟后缀pj-kp-1p匹配,如 果pkp失配,下一步就是用 plnexttk]去p继续匹配,如果 PL next[k]跟还是不匹配,则需要寻找长度更短的相同前缀后缀,即下一步用 of next[ next [k]]去跟j匹配。此过程相当于模式串的自我匹配,所以不断的递归κ=ηexk,直到嫛么找到长庋更短的相冋前缀后绶,要么没有长度更短的相同前缀后缀。如 下图乐示 P next[k 所以,因最终在前缀ABC中没有找到D,故E的next值为0 模式串的后缀:ABDE 模式串的前缀:ABC 前缀右移两位:ABC 读到此,有的读者可能又有疑问了,那能否举一个能在前缀中找到字符D的例子呢?K,咱们便来看一个能在前缀中找到字符D的例子,如下图所示 模式串 D A B C D A D 最长相同 ? 前缀后缀 0 0 next 值10000123 索引 pK Pi-k pi-a p 给定模式串 DABCDABDE,我们很顺利的求得字符D之前的" DABCDAB的各个子串的最长相同前缀后缀的长度分别为0000123,但当遍力到字符D,要求包 括D在内的 DABCDABD最长相同前缀后缀时,我们发现处的字符D跟pk处的字符C不一样,换言之,前级DABC的最后一个字符C跟后缀DABD的最后一个字符D 不相同,所以不存在长度为4的相同前缀后缀 怎么办呢?既然没有长度为4的相同前缀后缀,咱们可以寻找长度短点的相同前缀后缀,最终,因在p0处发现也有个字符D,p0=pj,所以p对应的长度值为1 相当于E对应的next值为1(即字符之前的字符串 DABCDABD中有长度为1的相同前缀和后缀)。 综上,可以通过递推求得next数组,代码如下所示 1 void GetNext( char* p, int next[l int pLen strlen(p); next[8]=-1 int k=-1: intj=0 /pk)表示前级,p[订表示后级 if(k==-1|p[j]==p[k]) 11 ++k next[j]=k; 16 18 k = nextlk] 21 用代码重新计算下" ABCDABD"的ηext数组,以验证之前通过“最长相同前缀后缀长度值右移一位,然后初值赋为-1得到的next数组是否正确, 计算结果如下表格所示 模式串 D A B D k -120 -1,0 0 1 4 6 next数组 0 0 0 2 从上述表格可以看出,无论是之前通过最长相同前缀后缀长度值右移一位,然后初值赋为-1得到的next数组,还是之后通过代码递推计算求得的next数组,结 果是完全一致的。 335基于《next数组》匹配 下面,我们来基于next数组进行匹配。 A xt值 还是给定文本串" BBC ABCDAB ABCDABCDABDE”,和模式串" ABCDABD”,现在要拿模式串去眼文本串匹配,如下图所示 BBC ABCDAB ABCDABCDABDE ABCDABD 在正式匹配之前,让我们来再次回顾下上文2.1节所述的KMP算法的匹配流程 “假设现在文本串S匹配到i位置,模式串P匹配到j位置 如果j=-1,或者当前字符匹配成功(即S==P]),都令++,+,继续匹配下一个字符 如果j=-1,且当前字符匹配失败(即S′=P),则令不变,j=nex。此举意味着失配时,模式串P相对于文本串S向右移动了j-net团位。 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置-失配字符对应的next值,即移动的实际位数为:j- nextEl,且此值大于 等于 ·1.最开始匹配时 ·P[o跟S0J匹配失败 所以执行如=-1,且当前字符匹配失败(即S!=P]),则令i不变,j=next",所=-1,故转而执行如果=-1,或者当前字符匹配成功 (即。==P]),都令++,++”,得到=1,j=0,即P[继续跟S[1匹配 P[0]跟S[又失配,j次等于-1,i、j继续自增,从而P[0跟S[2匹配。 P[O跟S[2]失配后,P[0]又跟S[3]匹配 ·Po跟S3再失配,直到P跟S[4匹配成功,开始执行此条指令的后半段:如果=-1,或者当前字符匹配成功(即S[==門),都令i++,j+"

...展开详情
试读 18P 从头到尾彻底理解KMP
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 技术圈认证

      用户完成年度认证,即可获得
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    从头到尾彻底理解KMP 38积分/C币 立即下载
    1/18
    从头到尾彻底理解KMP第1页
    从头到尾彻底理解KMP第2页
    从头到尾彻底理解KMP第3页
    从头到尾彻底理解KMP第4页
    从头到尾彻底理解KMP第5页
    从头到尾彻底理解KMP第6页

    试读已结束,剩余12页未读...

    38积分/C币 立即下载 >