KMP算法详解(课堂PPT)课件.ppt

《KMP算法详解(课堂PPT)课件.ppt》由会员分享，可在线阅读，更多相关《KMP算法详解(课堂PPT)课件.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1本PPT格式说明：代码全部以图片形式给出字符串样例全部以courier new字体给出注释全部以华文细黑华文细黑字体给出文字讲解以微软雅黑或verdana字体给出数学公式中的括号全部为半角括号()文字性解释说明中的括号全部为中文全角括号（）23abababcdabcdbbacabacaababaca4abababcdabcdbbacabacaababaca5abababcdabcdbbacabacaababaca6abababcdabcdbbacabacaababaca7abababcdabcdbbacabacaababaca8abababcdabcdbbacabacaababaca事实上，

2、我们在之前匹配的过程中已经知道了s2=bp1=a，i,j都回溯必然失配。那怎样降低时间复杂度呢？引入KMP算法，使用这个算法可以将上面O(nm)的复杂度降低为O(n+m)。KMP算法的核心思想是：文本串s的指针i不回溯。那是不是只需要在暴力的基础上保持失配时i不变就行了呢？你会发现：还是浪费了很多时间。有没有一种方法可以在失配时让j直接跳到一个应该跳到的位置上去呢？9这就来到KMP的大核心next数组。next数组表示的意思是当前字符之前的子串中最长相同前缀后缀的长度。说人话：当前字符之前模式串P子串最长相同前缀后缀的长度。手写个小Demo演示一下：abaabcanext 0 0 0 1 1

3、2 0注：一个字符串的相同前缀后缀是不包括这个字符串本身的，比如字符串”ab”，它就没有相同前缀后缀，字符串”a”同理。10next的意义：如果当前两个字符失配，那么模式串P应该移动到哪，换言之，应该用P中的哪个字符来继续匹配si。保证文本串S的指针i不回溯。next的求解：不必每次记录前缀后缀，前面匹配成功的字符，后面可以直接拿来用。为什么求一个相同最长前缀后缀长度就可以解决这个问题：假设在模式串红色位置失配：a b a a a b a c b c失配了，j要回溯，也就是模式串相对于文本串要右移。右移多少位呢？我们发现，既然当前位置前面的所有字符都匹配成功，那么它最长相同前缀后缀上的字符也都

4、相同。这些相同前缀后缀上的字符不需要再匹配，用这之中前缀的后面一个字符匹配当前字符即可，即失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。11算法一的错误之处在于：如果出现没出现过的字符，会陷入死循环。abaabcanext 0 0 0 1 1 ?12/i/i为为nextnext的下标，的下标，t t为为nextnext的值的值/-1/-1和和0 0都表示没有相同的前缀后缀都表示没有相同的前缀后缀/t=-1/t=-1同样可以达到同样可以达到next1=0next1=0的效果，想想为什么的效果，想想为什么/从从1 1到到(lenp-1)(lenp-1)枚

5、举枚举i i/赋值赋值nextnext/如果这是一个新字符如果这是一个新字符(t=-1)(t=-1)那么就赋值那么就赋值nextinexti为为0 0（-1+1=0-1+1=0）。）。t=nexttt=nextt的含义其实是的含义其实是t=nextt-1+1t=nextt-1+1。a b a a b c anext -1 0 0 1 1 2 0i13求完了next数组，下面就可以开始KMP了。模拟之前提到的过程就可以，可以总结为下面两条规则：规则一：如果匹配成功，i+,j+；规则二：如果失配，i不动，j回溯到nextj。代码十分容易理解，可能需要解释的就是输出模式串所在位置的条件，详见下页。14/规则一规则一/规则二规则二/如果模式串最后一个字符也匹配成功就输出这个如果模式串最后一个字符也匹配成功就输出这个/合法位置合法位置如果整个模式串匹配成如果整个模式串匹配成功，功，j j要回溯到要回溯到nextjnextj。15至此，KMP算法介绍结束。时间复杂度O(lens+lenp)。16谢谢谢谢