KMP算法讲解之——不需要公式-就能理解KMP算法PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,KMP,算法,20XX.XX.XX,汇报人：,XXX,1,2025/4/30 周三,汇报提纲,KMP,算法,一,.KMP,背景介绍,三,.KMP,核心,跳转表,next,二,.,由朴素匹配到,KMP,四,.next,的计算,引入,f(j),2,2025/4/30 周三,KMP,算法,一,.KMP,背景介绍,在文本编辑中，我们经常要在一段文本中某个特定的位置找出某个,特定的字符或模式,。再比如，在,HTTP,协议里的字节流,有各种关键的字节流字段,对,HTTP,数据进行解释就需要用到模式匹配算法。由此，便产生了,字符串的匹配,问题。,KMP,算法是由,Knuth,，,Morris,，,Pratt,三人,共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。,3,2025/4/30 周三,KMP,算法,二,.,由朴素匹配到,KMP,假设有,目标字符串,(Target),T=,b a b c b a b c a b c a a b c a b c a b c a c a b c,，我们要在其中找到,模式字符串（,Pattern,）,P=a b c a b c a c a b,。,如何做更为高效呢？,由朴素匹配，我们要做,16,次,，而,KMP,算法仅匹配了,6,次,就找到了模式字符串,朴素匹配的时间复杂度为,O(m*n),；,KMP,的时间复杂度为,O(n),。,4,2025/4/30 周三,KMP,算法,三,.KMP,算法核心,跳转表,next,其实，模式串往往含有一定的信息,前缀包含,。,对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为,前缀包含问题,。,那么每次要跳跃多少呢？这,与跳转表,next,存储的数值相关,。,以模式串,a b c a b c a c a b,为例，其前缀的,4,个字符,a b c a,，正好也是模式串的一个子串,a b c(,a,b c a,),c,a b,，所以当目标串与模式串执行匹配的过程中，如果直到第,8,个字符才匹配失败，同时也意味着,目标串,当前字符,之前的,4,个字符，与模式串的前,4,个字符是相同的,，所以当模式串向后移动的时候，可以直接将模式串的第,5,个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。,5,2025/4/30 周三,KMP,算法,三,.KMP,算法核心,跳转表,next,模式字符串,P=,a b c a b c a c a b,，其跳转表为：,6,2025/4/30 周三,KMP,算法,三,.KMP,算法核心,跳转表,next,我们以,KMP,匹配的,第,3,步,为例,:,此时,pattern,串的第,1,个字母与,target6,对齐，从,6,向后依次匹配目标串，到,target13,时发现,target13=a,，而,pattern8=c,，匹配失败，此时,next8=5,，所以将模式串向后移动,8-next8=3,个字符，将,pattern5,与,target13,对齐，然后由,target13,依次向后执行匹,配操作。在整个匹配过程中，无论模式串如何向后滑动，目标串的输入字符都,不会回溯,，直到找到模式串，或者遍历整个目标串都没有发现匹配模式为止。,7,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),跳转表,next,是,如何计算,的呢？以及怎样以,较小的代价,计算,?,这里我们引入一个概念,f(j),，其含义是，对于模式串的第,j,个字符,patternj,，,f(j),是所有满足使,pattern1,k-1,=patternj-(k-1),j-1,(k j),成立的,k,的,最大值,。,f(j)=k,我们可以看出,k,最小为,2,，,因此，规定,f(1)=0,；,不存在前缀包含时，,f(j)=1,模式字符串,P=,a b c a b c a c a b,的,f(j),计算结果如下：,8,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),f(j),含义：对于模式串的第,j,个字符,patternj,，,f(j),是所有满足使,pattern1,k-1,=patternj-(k-1),j-1,(k j),成立的,k,的,最大值,。,f(j)=k,比如，假设一个,11,位模式字符串为,a b,a b,c d,a b,a b,g,，则,f(11)=5!=3,。,如何理解取,K,最大值呢？,通过上图，我们不难看出，,k,越小，跳跃的步伐越大，很可能会把满足条件的匹配结果跳过去，因此我们在,保证算法快速的同时，还要保证准确！,9,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),为了说明,f(j),和,nextj,之间的关系，我们以,pattern8,为例，假如匹配到,pattern8,才匹配失败。,f(8)=5,pattern14=pattern47,，此时我们需要关注,pattern8,：,1.,如果,pattern8!=pattern5,因为在匹配到,pattern8,时才失败，此时就可以将输入字符,targetn,与,patternf(8)=pattern5,对齐，再向后依次执行匹配，所以此时的,next8=f(8),。,10,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),2.,如果,pattern8=pattern5,那么,pattern15=pattern48,，因为,targetn,与,pattern8,匹配失败，那么也意味着,targetn-4n!=pattern48,，那么将,targetn,与,pattern5,对齐，,targetn-4n,也必然,不等于,pattern15,。,此时我们需要关注,f(5),。,11,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),2.,如果,pattern8=pattern5,f(5)=2,，这意味着,pattern1=pattern4,，因为,pattern14=pattern47,，所以,pattern4=pattern7=pattern1,此时我们再来比较,pattern8,和,pattern2,。,2.1,如果,pattern8!=pattern2,就可以将,target2,与,pattern2,对齐，然后比较二者是否相等，此时,next8=nextf(8)=next5=f(5),。,12,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),2.2,如果,pattern8=pattern2,那么还需要考察,patternf(2),，,直到回溯到模式串头部为止。,13,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),由以上分析，我们可以归纳出根据,f(j),求,nextj,的,递推公式,：,如果,patternj!=patternf(j),，,nextj=f(j);,如果,patternj=patternf(j),，,nextj=nextf(j);,14,2025/4/30 周三,KMP,算法,四,.next,的计算,引入,f(j),15,2025/4/30 周三,谢 谢,学 号：,XXXXXXXX,汇报人：,XXX,班 级：,XXXXX,16,2025/4/30 周三,