KMP是什么意思-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

KMP是什么意思

知与谁同 2018-07-21 20:36:31 1122
KMP是什么意思
分享到
取消 提交回答
全部回答(2)
  • 祁同伟
    2019-07-17 22:56:01
    kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。 完全掌握KMP算法思想   学过数据结构的人,都对KMP算法印象颇深。尤其是新手,更是难以理解其涵义,搞得一头雾水。今天我们就来面对它,不将它彻底搞懂,誓不罢休。   如今,大伙基本上都用严蔚敏老师的书,那我就以此来讲解KMP算法。   严老的《数据结构》79-84页讲了基本的匹配方法,这是基础。先把这个搞懂了。   80页在讲KMP算法的开始先举了个例子,让我们对KMP的基本思想有了最初的认识。目的在于指出“由此,在整个匹配的过程中,i指针没有回溯,”。   在此也推荐张铭、赵海燕、王腾蛟编著的《数据结构与算法》一书(北京大学出版社),里面的“字符串”一章对KMP算法有较为详尽易懂的介绍。
    0 0
  • 云篆
    2019-07-17 22:56:01
    一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ,匹配时间为Θ(n),只用到辅助函数π[1,m],它是在Θ(m)时间内,根据模式预先计算出来的。数组π使得我们可以按需要,“现场”有效的计算(在平摊意义上来说)变迁函数δ。粗略地说,对任意状态q=0,1,…,m和任意字符a∈Σ,π[q]的值包含了与a无关但在计算δ(q,a)时需要的信息。由于数组π只有m个元素,而δ有Θ(m∣Σ∣)个值,所以通过预先计算π而不是δ,使得时间减少了一个Σ因子。
    0 0
添加回答
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

推荐文章