KMP算法详解(课堂PPT)_第1页
KMP算法详解(课堂PPT)_第2页
KMP算法详解(课堂PPT)_第3页
KMP算法详解(课堂PPT)_第4页
KMP算法详解(课堂PPT)_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论