KMP算法是什么?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 从上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可以预处理出这样一个数组P[j],表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。 再后来,A[7]=B[5],i和j又各增加1。这时,又出现了A[i+1]<>B[j+1]的情况: 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 由于P[5]=3,因此新的j=3: 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 这时,新的j=3仍然不能满足A[i+1]=B[j+1],此时我们再次减小j值,将j再次更新为P[3]: 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 现在,i还是7,j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样,j必须减小到P[1],即0: 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 = 0 1 2 3 4 5 6 7 终于,A[8]=B[1],i变为8,j为1。事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]="d"时)。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。 这个过程的代码很短(真的很短),我们在这里给出: j:=0; for i:=1 to n do begin while (j>0) and (B[j+1]<>A[i]) do j:=P[j]; if B[j+1]=A[i] then j:=j+1; if j=m then begin writeln("Pattern occurs with shift ",i-m); j:=P[j]; end; end;最后的j:=P[j]是为了让程序继续做下去,因为我们有可能找到多处匹配。 这个程序或许比想像中的要简单,因为对于i值的不断增加,代码用的是for循环 。因此,这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。 现在,我们还遗留了两个重要的问题:一,为什么这个程序是线性的;二,如何快速预处理P数组。 为什么这个程序是O(n)的?其实,主要的争议在于,while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略,简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小(但不能减成负的),而另外的改变j值的地方只有第五行。每次执行了这一行,j都只能加1;因此,整个过程中j最多加了n个1。于是,j最多只有n次减小的机会(j值减小的次数当然不能超过n,因为j永远是非负整数)。这告诉我们,while循环总共最多执行了n次。按照摊还分析的说法,平摊到每次for循环中后,一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效,同样可以得到预处理过程的复杂度为O(m)。 预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],…,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb",假如我们已经求出了P[1],P[2],P[3]和P[4],看看我们应该怎么求出P[5]和P[6]。P[4]=2,那么P [5]显然等于P[4]+1,因为由P[4]可以知道,B[1,2]已经和B[3,4]相等了,现在又有B[3]=B[5],所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗?显然不是,因为B[ P[5]+1 ]<>B[6]。那么,我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到,即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下: 1 2 3 4 5 6 7 B = a b a b a c b P = 0 0 1 2 3 ? P[5]=3是因为B[1..3]和B[3..5]都是"aba";而P[3]=1则告诉我们,B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到,或许可以由P[3]得到(如果B[2]恰好和B[6]相等的话,P[6]就等于P[3]+1了)。显然,P[6]也不能通过P[3]得到,因为B[2]<>B[6]。事实上,这样一直推到P[1]也不行,最后,我们得到,P[6]=0。 怎么这个预处理过程跟前面的KMP主程序这么像呢?其实,KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似: P[1]:=0; j:=0; for i:=2 to m do begin while (j>0) and (B[j+1]<>B[i]) do j:=P[j]; if B[j+1]=B[i] then j:=j+1; P[i]:=j; end;最后补充一点:由于KMP算法只预处理B串,因此这种算法很适合这样的问题:给定一个B串和一群不同的A串,问B是哪些A串的子串。 串匹配是一个很有研究价值的问题。事实上,我们还有后缀树,自动机等很多方法,这些算法都巧妙地运用了预处理,从而可以在线性的时间里解决字符串的匹配。我们以后来说。 昨天发现一个特别晕的事,知道怎么去掉BitComet的广告吗?把界面语言设成英文就行了。 还有,金山词霸和Dr.eye都可以去自杀了,Babylon素王道。 Matrix67原创
标签:
相关推荐:
最新新闻:
- 全球观焦点:系统冗余是什么?冗余的详情介绍
- 如何下载天地图离线地图瓦片数据?离线地图的下载方式
- 定时器和延时器的区别 定时器和延时器的异步语句|当前关注
- 【前沿重器】句子相似度和匹配心法利器 全球即时看
- 西门子PLC7怎么防止错误操作?西门子PLC梯形图编程规则
- WIN+R:程序运行窗口或者打开某个文件
- 正则解析网络运维数据之OneTake 解析网络运维数据:环球焦点
- 2023年常州春节哪里有烟花?:世界即时
- KMP算法是什么?KMP算法详解_全球消息
- 精选!《霍格沃茨之遗》发售1个月倒计时 社区总监:等待是艰难的
- 恐怖逃生解谜游戏《恶娑海》Steam页面上线 2023年第四季度发售_当前滚动
- 鹅鸭杀否认腾讯收购 尚未计划登陆WeGames-天天热推荐
- CCTV6将首播刘亦菲版《花木兰》 尽显东方神韵 世界观热点
- 环球实时:HBO《最后生还者》角色设定改动 山姆的耳朵失聪了
- 今日播报!索尼宣布推出《原神》联动耳机 仅在日本限定发售
- 罗琳引LGBTQ+不满 《霍格沃茨之遗》喜提“反派”tag
- 《幻想三国志 天元异事录》现已在Steam平台免费推出
- 微软《极限竞速:地平线》系列多位人才出走 成立全新工作室
- 《流浪地球2》IMAX/CINITY海报:风格独特宏伟壮观:环球观热点
- 庵野秀明将客串漫改日剧《一刑的乌鸦》剧场版
- 米哈游希望在2030年推出世界级元宇宙产品 10亿人可生活其中
- pdg用什么打开?怎样将pdg文件转为pdf?
- macbook截屏快捷键是什么?macbook截屏快捷键的方法
- win7没有找到Vcomp100.dll?找到Vcomp100.dll的具体步骤
- DNF如何设置窗口?设置DNF窗口的步骤
- skype登陆不上怎么办?skype登陆不上处理方法步骤
- xp系统无法关机是什么原因?无法关机的两种解决办法
- 提示80072efd的错误代码是怎么回事?提示80072efd的错误代码解决方法
- 没下载完的文件如何导入迅雷?迅雷提示"临时文件读取错误"?
- Win8系统配置在哪里?打开Win8系统配置步骤
- 电脑总是弹出Windows安全警告?教大家关闭安全警告的方法
- 初始化网卡信息失败导致不能上网怎么办?初始化网卡信息失败导致不能上网操作过程
- 一键还原精灵怎么彻底删除?一键还原精灵彻底删除两种方法及注意事项
- 会声会影x5序列号及激活码分享 会声会影x5安装步骤
- mom.exe是什么进程?mom.exe文件放在哪?
- 文件夹禁止写入怎么设置?文件夹中不可以存放什么?
- cdr文件打开很慢是什么原因导致的?cdr文件打开很慢的解决方法
- e站需要挂什么加速器 ehviewer网络错误怎么办?
- 设置点击此处进行编辑怎么设置?设置点击此处进行编辑设置操作步骤分享
- 蒲公英SD-WAN组网是什么?蒲公英如何异地组网?
- Win8怎么分区?Win8硬盘分区的方法
- 环球热消息:次世代版MSX迷你掌上主机样品公开 1月15日开众筹
- 《魔界战记7》第4弹宣传片公开 游戏1月26日发售-每日快报
- 世界速递!SpaceX运用医疗模拟游戏训练宇航员 效果明显
- 环球热文:《霍格沃茨之遗》Steam页面被打上二战、心里恐怖等标签 疑似粉丝抗议JK罗琳
- 动视暴雪拒绝承认子公司Proletariat工会成立
- 环球时讯:《英雄联盟》S13全球总决赛将在韩国举办 采取全新赛制
- 今日热讯:《死亡岛2》给武器加耐久度 是让玩家不断换新武器
- 任天堂日服试玩同乐会 《你裁我剪斯尼帕》免费游玩
- 《龙珠Z:卡卡罗特》巴达克DLC新预告 1月13日推出|每日热文
- 环球即时:3天内获3万辆汽车订单?特斯拉回应不予置评
- 电脑显卡正常温度范围是多少?显卡正常温度介绍
- LOL提示登录失败请重试是怎么回事?原因分析及解决方法
- 电脑开机总是弹出360热点新闻怎么办?360热点资讯怎么彻底删除?
- 思科tftp服务器如何设置根目录?思科tftp服务器命令介绍
- QQ缓存文件是什么?QQ缓存文件应该怎么清除?
- 浏览器提示无法定位序数459怎么办?教大家解决方法
- 提示此网页包含的内容将不使用安全的https连接传送怎么解决?
- bios电池在哪?找寻bios电池在哪的方法步骤
- 产的了却买不到的布洛芬,到底是不是个投资新机会? | MIR DATABANK|新要闻
- 磁盘碎片整理有什么用?介绍磁盘碎片整理的作用
- 打开方式不对导致文件打不开怎么办?还原文件默认打开方式步骤
- coreldraw复制快捷键是什么?cdr怎么等距离连续复制?
- 虚拟光驱怎么用?虚拟光驱的使用方法步骤
- 提示vcomp100.dll丢失问题怎么解决?Vcomp100.dll丢失解决方法
- skype无法登录怎么办?skype无法登录的操作方法
- 电脑提示Shockwave Flash崩溃怎么解决?三种解决方法
- 一直弹出ravmond.exe应用程序错误怎么办?ravmond.exe应用程序错误解决方法
- 如何打开PDG格式文件?PDG文件的打开方法
- 《最后的生还者》剧集IGN评9分 吸取了游戏精髓
- 统计显示自2016年以来 英国游戏公司增长了31%_世界报资讯
- 焦点速读:直击JPM:吉利德因涨价遭现场抗议;辉瑞全球CEO回应P药在华策略;强生、BMS手握收购巨资……
- 1999 元!大疆 RS 3 Mini 微单稳定器发布:真的很迷你
- 苹果罕见大气发福利!iPhone、iPad送半年iCloud+ 每日关注
- 全球热讯:性能怪兽来了 RTX40系显卡水冷游戏本发布