KMP算法详解课件.ppt

1、b,1,本PPT格式说明： 代码全部以图片形式给出 字符串样例全部以courier new字体给出 注释全部以华文细黑字体给出 文字讲解以微软雅黑或verdana字体给出 数学公式中的括号全部为半角括号() 文字性解释说明中的括号全部为中文全角括号（）,b,2,KMP,Knuth-Morris-Pratt字符串匹配查找算法,b,3,b,4,b,5,b,6,b,7,b,8,事实上，我们在之前匹配的过程中已经知道了s2=bp1=a，i,j都回溯必然失配。,那怎样降低时间复杂度呢？,引入KMP算法，使用这个算法可以将上面O(nm)的复杂度降低为O(n+m)。,KMP算法的核心思想是：文本串s的指针i

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

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

4、现没出现过的字符，会陷入死循环。,next 0 0 0 1 1 ?,b,12,/i为next的下标，t为next的值,/-1和0都表示没有相同的前缀后缀,/t=-1同样可以达到next1=0的效果，想想为什么,/从1到(lenp-1)枚举i,/,/赋值next,/,如果这是一个新字符(t=-1)那么就赋值nexti为0（-1+1=0）。,t=nextt的含义其实是t=nextt-1+1。,next -1 0 0 1 1 2 0,b,13,求完了next数组，下面就可以开始KMP了。,模拟之前提到的过程就可以，可以总结为下面两条规则： 规则一：如果匹配成功，i+,j+； 规则二：如果失配，i不动，j回溯到nextj。,代码十分容易理解，可能需要解释的就是输出模式串所在位置的条件，详见下页。,b,14,/规则一,/规则二,/如果模式串最后一个字符也匹配成功就输出这个,/合法位置,如果