开发者社区> 问答> 正文

KMP是什么意思

KMP是什么意思

展开
收起
知与谁同 2018-07-21 20:36:31 4646 0
2 条回答
写回答
取消 提交回答
  • 胜天半子
    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算法有较为详尽易懂的介绍。
    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∣Σ∣)个值,所以通过预先计算π而不是δ,使得时间减少了一个Σ因子。
    2019-07-17 22:56:01
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载