大学数据结构课件10.KMP.pptVIP

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
kmp算法 kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与J.H.Morris和 V.R.Pratt同时发现,因此人们称它为克努斯——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串p(pattern),定义一个next函数。next函数包含了模式串本身局部匹配的信息。 KMP算法的基本思想   一般的KMP算法 假设 主串: s: ‘s(1) s(2) s(3) ……s(n)’ 模式串 :p: ‘p(1) p(2) p(3)…... p(m)’ 现在我们假设 主串第i个字符与模式串的第j(j=m)个字符‘失配’(不同)后,主串第i个字符与模式串的第k(kj)个字符继续比较(为什么?) 此时,s(i)≠p(j), 有 主串:s(1) … s(i-j+1) s(i-j+2) … s(i-1) s(i) … … || (相配) || ... || ≠(失配) (1) 匹配串: p(1) p(2) ... p(j-1) p(j) … 由此,我们得到关系式:   ‘p(1) p(2) … p(j-1)’ = ’ s(i-j+1) s(i-j+2) … s(i-1)’ (2) 一般的KMP算法 由于s(i)≠p(j),接下来如果将s(i) 与p(k) (kj)继续比较,则模式串中的前(k-1)个字符子串必须等于主串第i个字符前的(k-1)个字符子串,并且不可能存在 kk (kj)也满足上述关系。即: ‘p(1) p(2) p(3)…p(k-1)’ = ’s(i-k+1)s(i-k+2)…s(i-1)’ (3) 即: 主串: s(1)…s(i-k+1) s(i-k +2) … s(i-1) s(i) … || (相配) || … || ? (有待比较) 匹配串: p(1) p(2) … p(k-1) p(k) 由(1)、(2)式可知,若 ‘p(1) p(2) … p(k-1)’ = ’p(j-k+1)p(j-k+2) … p(j-1)’ (4) 则(3)式一定成立。(为什么?) 一般的KMP算法 因为: s(i)≠p(j) 主串:s(1) … s(i-j+1) s(i-j+2) … s(i-1) s(i) … … || (相配) || ... || ≠(失配) (1) 匹配串: p(1) p(2) ... p(j-1) p(j) … ‘p(1) p(2) … p(j-1)’ = ’ s(i-j+1) s(i-j+2) … s(i-1)’ (2) (2)式说明:主串中第i个字符前的j-1个字符子串等于匹配串中第j个字符前的j-1个字符子串。因为 k j , 所以主串中第i个字符前的k-1个字符子串必然等于匹配串中第j个字符前的k-1个字符子串。即: ‘p(j-k+1) p(j-k+2) … p(j-1)’ = ’ s(i-k+1) s(i-k+2) … s(i-1)’ (5) 如果匹配串中第k个字符前的k-1个字符子串等于匹配串中第j个字符前的k-1个字符子串,即: ‘p(1) p(2) … p(k-1)’ = ’p(j-k+1)p(j-k+2) … p(j-1)’ (4) 由上列(4)、(5)两式,自然推出: ‘p(1) p(2) … p(k-1)’ = ’s(i-k+1)s(i-k+2) … s(i-1)’ (3) 一般的KMP算法 前面总结的关系可综合如下 : 有:   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)   

文档评论(0)

dart001 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档