文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > KMP算法详解
侵权投诉

KMP算法详解

KMP

KMP算法思想

80页在讲KMP算法的开始先举了个例子,让我们对KMP的基本思想有了最初的认识。目的在于指出“由此,在整个匹配的过程中,i指针没有回溯,”。 我们继续往下看: 现在讨论一般情况。

假设 主串:s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 :p: ‘p(1) p(2) p(3)…..p(m)’

把课本上的这一段看完后,继续现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后,主串第i个字符与模式串的第k(k<j)个字符继续比较此时,s(i)≠p(j), 有

主串: S(1)…… s(i-j+1)…… s(i-1) s(i) …………. || (相配) || ≠(失配) 匹配串: P(1) ……. p(j-1) p(j) 由此,我们得到关系式

‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’

由于s(i)≠p(j),接下来s(i)将与p(k)继续比较,则模式串中的前(k-1)个字符的子串必须满足下列关系式,并且不可能存在 k’>k 满足下列关系式:(k<j),

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’ 即:

主串: S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) …………. || (相配) || || ?(有待比较) 匹配串: P(1) p(2) …… p(k-1) p(k) 现在我们把前面总结的关系综合一下有:

S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) …… || (相配) || || || ≠(失配) P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j) || (相配) || || ?(有待比较) P(1) p(2) ……. p(k-1) p(k) 由上,我们得到关系:

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’

接下来看“反之,若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段,如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)

K 是和next有关系的,不过在最初看的时候,你不要太追究k到底是多少,至于next值是怎么求出来的,我教你怎么学会。课本83页不是有个例子吗?就是 图4.6

你照着源程序,看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。

然后找几道练习题好好练练,一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了,再回去看它是怎么推出来的,如果还看不懂,就继续做练习,做完练习再看。相信自己!!!

我们这里说的KMP不是拿来放电影的(虽然我很喜欢这个软件),而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串)。比如,字符串A="I'm matrix67",字符串B="matrix",我们就说B是A的子串。你可以委婉地问你的MM:“假如你要向你喜欢的人表白的话,我的名字是你的告白语中的子串吗?”

解决这类问题,通常我们的方法是枚举从A串的什么位置起开始与B匹配,然后验证是否匹配。假如A串长度为n,B串长度为m,那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn(验证时只看头一两个字母就发现不匹配了),但我们有许多“最坏情况”,比如,A= "aaaaaaaaaaaaaaaaaaaaaaaaaab",B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法(这里假设 m<=n),即传说中的KMP算法。

之所以叫做KMP,是因为这个算法是由Knuth、Morris、Pratt三个提出来的,取了这三个人的名字的头一个字母。这时,或许你突然明白了AVL 树为什么叫AVL,或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过,那怎么命名呢?通常这个东西干脆就不用人名字命名了,免得发生争议,比如“3x+1问题”。扯远了。

个人认为KMP是最没有必要讲的东西,因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念,这非常容易产生误解(至少一年半前我看这些资料学习KMP时就没搞清楚)。在这里,我换一种方法来解释KMP

第1页

热门文档

相关文档

  • KMP算法详解0.0

    KMP算法详解0.0_工学_高等教育_教育专区。KMP next nextval字符串匹配算法分析—KMP 算法这里就只说一下这个 KMP 算法的核心, 就是把要查找串改编成一串 NEXT...

  • KMP算法详解

    () 运行结果,如下图所示: 代码实现二: 再给出代码实现二之前,让我们再次回顾下关于 KMP 算法的第一篇文章中 的部分内容: “第二节、KMP 算法 2.1、 覆盖...

  • KMP算法解析

    KMP算法解析_计算机/互联网_科技_PPT专区。简单的快速查找算法,目的:一个字符串中查找匹配的字串KMP算法解析 引出模式串的next函数: ? ? ? ? ? ? ? T t0...

  • kmp算法详解(Matrix67原创)

    我们将介绍的是一种最 坏情况下 O(n)的算法(这里假设 m<=n) ,即传说中的 KMP 算法。 之所以叫做 KMP,是因为这个算法是由 Knuth、Morris、Pratt 三个提...

  • KMP算法详解 by Matrix67

    KMP算法详解 by Matrix67_IT/计算机_专业资料。信息学竞赛的经典之作,每一个OIer都应个读过的作品,北大文科生&NOI2006银牌得主的作品 字符串处理方面著名的KMP...

  • KMP算法详解

    KMP算法详解_IT/计算机_专业资料。详细讲解KMP算法。(1)以一个例子引入 (1)以一个例子引入 KMP 算法 先看朴素模式匹配过程: 先看朴素模式匹配过程: (a)S:...

  • KMP算法解析

    KMP算法解析_法律资料_人文社科_专业资料。本文针对KMP算法,给出最全面最容易理解的分析与演示,给出学者以学习。KMP 算法解析 说明:为讲解方便,我们假设需要在主...

  • 严蔚敏 数据结构 kmp算法详解

    严蔚敏 数据结构 kmp算法详解_计算机软件及应用_IT/计算机_专业资料。4.3.2 KMP算法 KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt 共同提出的,简称KMP算法...

  • KMP算法

    关于传统算法以及kmp算法的讲解、实现以及复杂度分析关于传统算法以及kmp算法的讲解、实现以及复杂度分析隐藏>> 4.4 串的模式匹配算法 一、基本概念 1、模式匹配(...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email