KMP算法详解课堂.ppt

2 KMP Knuth-Morris-Pratt 字符串匹配查找算法 3 abababcdabcdbbacabacaab S abaca P 4 abababcdabcdbbacabacaab S abaca P 5 abababcdabcdbbacabacaab S abaca P 6 abababcdabcdbbacabacaab S abaca P 7 abababcdabcdbbacabacaab S abaca P 8 abababcdabcdbbacabacaab S abaca P 事实上，我们在之前匹配的过程中已经知道了 s[2]=b ≠ p[1]=a ， i,j 都回 溯必然失配。 那怎样降低时间复杂度呢？ 引入 KMP 算法，使用这个算法可以将上面 O(nm) 的复杂度降低为 O(n+m) 。 KMP 算法的核心思想是：文本串 s 的指针 i 不回溯。 那是不是只需要在暴力的基础上保持失配时 i 不变就行了呢？ 你会发现：还是浪费了很多时间。 有没有一种方法可以在失配时让 j 直接跳到一个应该跳到的位置上去呢？ 9 这就来到 KMP 的大核心 —— next 数组。 next 数组表示的意思是当前字符之前的子串中最长相同前缀后缀的长度。 说人话：当前字符之前模式串 P 子串最长相同前缀后缀的长度。 手写个小 Demo 演示一下： abaabca P next 0 0 0 1 1 2 0 注：一个字符串的相同前缀后缀是不包括这个字符串本身的，比如字符 串 ”ab” ，它就没有相同前缀后缀，字符串 ” a ” 同理。 10 next 的意义： 如果当前两个字符失配，那么模式串 P 应该移动到哪，换言之，应该用 P 中的哪个字符来继续匹配 s[i] 。保证文本串 S 的指针 i 不回溯。 next 的求解： 不必每次记录前缀后缀，前面匹配成功的字符，后面可以直接拿来 用。 为什么求一个相同最长前缀 后缀长度就可以解决这个问 题： 假设在模式串红色位置失配： a b a a a b a c b c 失配了， j 要回溯，也就是模 式串相对于文本串要右移。 右移多少位呢？我们发现， 既然当前位置前面的所有字 符都匹配成功，那么它最长 相同前缀后缀上的字符也都 相同。这些相同前缀后缀上 的字符不需要再匹配，用这 之中前缀的后面一个字符匹 配当前字符即可，即失配时， 模式串向右移动的位数为： 已匹配字符数 - 失配字符的 上一位字符所对应的最大长 度值。 11 算法一的错误之处在于：如果出现没出现过的字符，会陷入死循环。 abaabca P next 0 0 0 1 1 ? 12 //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 。 a b a a b c a P next -1 0 0 1 1 2 0 i t 13 求完了 next 数组，下面就可以开始 KMP 了。 模拟之前提到的过程就可以，可以总结为下面两条规则： 规则一：如果匹配成功， i++,j++ ； 规则二：如果失配， i 不动， j 回溯到 next[ j] 。 代码十分容易理解，可能需要解释的就是输出模式串所在位置的条件， 详见下页。