文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > matrix67blog中关于kmp匹配算法的解释文章
侵权投诉

matrix67blog中关于kmp匹配算法的解释文章

KMP算法详解

如果机房马上要关门了,或者你急着要和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算法详解csdn

    前 2 个位置,继续匹配的过程,这就是 KMP 算法...而那个 Max 是什么意思,举个例子: T:aaab ......查看最新精华文章 请访问博客首页相关文章 ) ...

  • kmp模式匹配算法

    28 个人觉得这篇文章是网上的介绍有关 KMP 算法更...(j)的说法,其实是一个意思,即 next[j]=f(j-1...对于一般文稿中串的匹配,简单匹配算法的时间复杂度可...

  • 关于KMP算法和BM算法的理解

    关于KMP 算法和 BM 算法的理解自己之前没有接触到...文章中主要讲的是多模式匹配算法: AC 算法和 WM ...这里我 们引入一个概念 f(j),其含义是,对于模式...

  • 经典KMP算法(易理解)

    这个就是在利用状态 机模型来解释 KMP 算法时的...中的字符和 M 中的字符不匹配时 S 要和 M 中...详情请参考 matrix67 大牛的文章,下面有犀利的评论:...

  • KMP算法详解 by Matrix67

    在这 里,我换一种方法来解释 KMP 算法. 假如,A="abababaababacb",B="aba...只与 B 串有关.我们完全可以预处理出 这样一个数组 P[j],表示当匹配到 B...

  • 模式匹配中的KMP算法的实现

    模式匹配中的KMP算法的实现_IT/计算机_专业资料。模式匹配中的KMP算法的实现数据结构课程设计 设计说明书 模式匹配中的 KMP 算法的实现 学生姓名学班成号级绩 ...

  • KMP算法详解

    由于此前,个人已经写过关于 KMP 算法 的两篇文章,所以,本文名为:KMP 算法之...多谢。 第一部分、KMP 算法初解 1、普通字符串匹配 BF 算法与 KMP 算法的...

  • KMP算法详解

    KMP 算法是拿来处理字符串匹配的。换 句话说,给你...比如,字符串 A="I'm matrix67",字符串 B="...在这里,我换一种方法来解释 KMP 2010-9-14 1/5...

  • 文学研究助手与模式匹配算法KMP

    KMP 算法在数据结构(C 语言版)中 的第 82 页有详细解释,在此不予以解释。我的大概思路是: 1.打开文件 2.输入想要匹配的一组字符串 3.读取文件的一行 4....

  • 一种改进的KMP高效模式匹配算法

    6页 免费 2、词类活用 2页 免费 KMP模式匹配算法的研究分析... 4页 免费...中图分类号! a D "!! 文献标识码!J!! 文章编号! & #" # !$ & #C...

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