文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > kmp算法详解(Matrix67原创)
侵权投诉

kmp算法详解(Matrix67原创)

如果机房马上要关门了,或者你急着要和MM约会,请直接跳到第六个自然段。

我们这里说的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算法。

假如,A="abababaababacb",B="ababacb",我们来看看KMP 是怎么工作的。我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们就 说B是A的子串(B串已经整完了),并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1],KMP的策略是调整j的位置 (减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加)。我们看一看当 i=j=5时的情况。

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B = a b a b a c b

j = 1 2 3 4 5 6 7

此 时,A[6]<>B[6]。这表明,此时j不能等于5了,我们要把j改成比它小的值j'。j'可能是多少呢?仔细想一下,我们发现,j'必须 要使得B[1..j]中的头j'个字母和末j'个字母完全相等(这样j变成了j'后才能继续保持i和j的性质)。这个j'当然要越大越好。在这里,

B [1..5]="ababa",头3个字母和末3个字母都是"aba"。而当新的j为3时,A[6]恰好和B[4]相等。于是,i变成了6,而j则变成了 4:

i = 1 2 3 4 5 6 7 8 9 ……

A = a b a b a b a a b a b …

B = a b a b a c b

j = 1 2 3 4 5 6 7

第1页

你可能喜欢

热门文档

相关文档

  • KMP算法详解 by Matrix67

    KMP算法详解 by Matrix67_IT/计算机_专业资料。信息学竞赛的经典之作,每一个...Matrix67原创 转贴请注明出处 3 今日推荐 180份文档 2014证券从业资格考试...

  • KMP算法详解 转帖

    KMP 算法详解 转帖 2010-02-24 12:05 个人觉得这篇文章是网上的介绍有关 ... 模式匹配的KMP算法详解(... 4页 1下载券 KMP算法详解 by Matrix6... 3...

  • KMP算法详解

    KMP算法详解_IT/计算机_专业资料。KMPKMP 材料 KMP 算法思想 80 页在讲 KMP...比如,字符串 A="I'm matrix67",字符串 B="matrix",我们就说 B 是 A ...

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

    严蔚敏 数据结构 kmp算法详解_计算机软件及应用_IT/计算机_专业资料。4.3.2... KMP算法(原创) 15页 免费 kmp算法课件演示(推荐) 17页 1下载券 next数组求...

  • KMP算法详解

    67. 68. 69. 70. 71. 72. 73. } } if (pattern_index==pattern_... KMP算法详解 by Matrix6... 3页 免费 模式匹配的KMP算法详解(... 4页 1...

  • KMP算法详解0.0

    字符串匹配算法分析—KMP 算法这里就只说一下这个 KMP 算法的核心, 就是把要... KMP算法详解 by Matrix6... 3页 免费 KMP算法c实现 4页 免费 KMP 算法 ...

  • KMP算法(原创)

    {i++;j++;} else {i = i-j+1;j = 0;} } if(j >= t.size-1) v = i-t.size+1; else v = -1; return v; } 模式匹配的KMP算法基本...

  • 详解KMP算法中Next数组的求法

    详解KMP算法中Next数组的求法_IT/计算机_专业资料。详解 KMP 算法中 Next ... KMP算法详解(NEXT数组修... 2页 免费 KMP算法详解 by Matrix6... 3页 ...

  • KMP算法详解(NEXT数组修正的补充)

    KMP算法详解(NEXT数组修正的补充)_理学_高等教育_教育专区。KMP算法详解(NEXT数组修正的补充)今日推荐 180份文档 CET四六级高分通关宝典...

  • 模式匹配的KMP算法详解csdn

    模式匹配的KMP算法详解csdn 本人学习数据结构时精心收藏的KMP编程文章本人学习数据结构时精心收藏的KMP编程文章隐藏>> 种由D.E.Knuth,J.H.Morris 和 V.R.Pratt...

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