KMP算法详解课件学习资料.ppt

《KMP算法详解课件学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KMP算法详解课件abababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaPabababcdabcdbbacabacaabSabacaP事实上，我们在之前匹配的过程中已经知道了s[2]=b≠p[1]=a，i,j都回溯必然失配。那怎样降低时间复杂度呢？引入KMP算法，使用这个算法可以将上面O(nm)的复杂度降低为O(n+m)。KM

2、P算法的核心思想是：文本串s的指针i不回溯。那是不是只需要在暴力的基础上保持失配时i不变就行了呢？你会发现：还是浪费了很多时间。有没有一种方法可以在失配时让j直接跳到一个应该跳到的位置上去呢？这就来到KMP的大核心——next数组。next数组表示的意思是当前字符之前的子串中最长相同前缀后缀的长度。说人话：当前字符之前模式串P子串最长相同前缀后缀的长度。手写个小Demo演示一下：abaabcaPnext0001120注：一个字符串的相同前缀后缀是不包括这个字符串本身的，比如字符串”ab”，它就没有相同前缀后缀，字符串”a”同理。next的意义：如果当前两个字符失配，

3、那么模式串P应该移动到哪，换言之，应该用P中的哪个字符来继续匹配s[i]。保证文本串S的指针i不回溯。next的求解：不必每次记录前缀后缀，前面匹配成功的字符，后面可以直接拿来用。为什么求一个相同最长前缀后缀长度就可以解决这个问题：假设在模式串红色位置失配：abaaabacbc失配了，j要回溯，也就是模式串相对于文本串要右移。右移多少位呢？我们发现，既然当前位置前面的所有字符都匹配成功，那么它最长相同前缀后缀上的字符也都相同。这些相同前缀后缀上的字符不需要再匹配，用这之中前缀的后面一个字符匹配当前字符即可，即失配时，模式串向右移动的位数为：已匹配字符数-失配字符的上

4、一位字符所对应的最大长度值。算法一的错误之处在于：如果出现没出现过的字符，会陷入死循环。abaabcaPnext00011?//i为next[]的下标，t为next[]的值//-1和0都表示没有相同的前缀后缀//t=-1同样可以达到next[1]=0的效果，想想为什么//从1到(lenp-1)枚举i//①//赋值next[]//②①如果这是一个新字符(t==-1)那么就赋值next[i]为0（-1+1=0）。②t=next[t]的含义其实是t=next[t]-1+1。abaabcaPnext-1001120it求完了next数组，下面就可以开始KMP了。模拟之前提到

5、的过程就可以，可以总结为下面两条规则：规则一：如果匹配成功，i++,j++；规则二：如果失配，i不动，j回溯到next[j]。代码十分容易理解，可能需要解释的就是输出模式串所在位置的条件，详见下页。//规则一//规则二//如果模式串最后一个字符也匹配成功就输出这个//合法位置如果整个模式串匹配成功，j要回溯到next[j]。至此，KMP算法介绍结束。时间复杂度O(lens+lenp)。谢谢~此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢