本文共 4155 字,大约阅读时间需要 13 分钟。
KMP算法可以说是知名度非常高的算法了,不管是数据结构课本还是各大论坛都对这个算法进行过深入讲解,但遗憾的是,还是把大部分人给劝退了。
如下有两个字符串,问你:如何快速在主串中找到目标串?
当然我们说的是算法,请你不要回答“肉眼搜索之类的话题”(当然如果这个主串有一亿个字符我相信你这辈子也不可能找出来)
回归正题,相信大家想到的第一个解决方法就是暴力破解——用两个指针,开始时分别指向两个串的开头,然后比较,如果相同继续扫描下一个字符,一旦出现不相同,两个指针进行回溯,主串的指针回溯到下一位,目标串的指针晦朔至第一位,然后继续按照上述步骤比较
直接用图片描述如下,需要注意的是,回溯的步骤在图中表示为了目标串向后移动的,但是实际物理内存中字符串是不可能移动的,这里只是为了形象解释
int index(string main_str,string aim_str){ int i=0; int j=0;//i和j分别用来扫描主串和目标串 while(i<=main_str.size()-1 && j<=aim_str.size()-1) { if(main_str[i]==main_str[j]) { ++i; ++j; } else { j=1; i=++k; } } if(j>aim_str.size()-1) return k; else return 0;}
暴力匹配是可行的,但是时间复杂度一看就很高,所以KMP算法正是为了解决如何快速在主串中找到目标串而生的,而且它真的很快。
为了便于介绍,我将主串和目标串设置为这样(当然,下面的例子中主串中是没有目标串的,但是不要紧,我只是为了说明更好的说明,有没有都一样)
通过上面的那么长的一张图,,大家可能已经发现了暴力匹配的缺陷所在——对,就是回溯太频繁了,只要找不到就回溯到下一位
所以KMP的算法的核心点就在这里:不要回溯到无效的地方,让其回溯到有效的位置
在讲下面前,必须引入一个概念——一个字符串的最长相同前缀和后缀。
关于这个问题,其实很多数据结构的书解释的都太过复杂了,甚至总是爱拿出一套公式把你劝退要想知道什么是最长相同前缀和后缀,首先得明白什么是字符串的前缀和后缀,看完下面这个图相信你就不难理解了
那么,最长相同前缀和后缀你也应该能找出来了吧
前面讲过,KMP算法的核心问题就是处理如何有效的回溯的问题。
再把之前那个应该这样回溯的图拿来,注意观察下面的话一定要认真理解,这是你是否能理解KMP算法以及明白为什么要有next数组的关键所在。首先请问目标串发生不匹配时的索引是多少?,是5对吧,然后咋们回溯的时候请问目标串的哪个位置(或者说索引)与主串的不匹配位置(也就是5)“对齐了”?很明显是目标串的2号位置,你有没有发现——这个2恰好就是目标串发生不匹配位置前的字符串的最长前缀和后缀的长度!
好的如何你能理解上面的部分,那么KMP算法的思想算是已经明白了。
进过上面的叙述,我们可以意识到,这种回溯是有规律的,并不是凭空臆想的。
再举几个例子 如下目标串的索引为3号的位置发生不匹配我们把目标串每个位置发生不匹配时,目标串应该回溯的位置给记录下来,形成一个数组,这个数组就是大名鼎鼎的next数组,next[i]=j,就表示索引为i的位置发生不匹配,就让其回溯的j的位置继续匹配
next数组的计算方法我其实前面已经说到过了,如下目标的串next数组计算如下,需要注意是由于第一个位置也就是next[0]前面没有串,所以记为-1
A | B | C | A | B | C | M | N |
---|---|---|---|---|---|---|---|
next[0] | next[1] | next[2] | next[3] | next[4] | next[5] | next[6] | next[7] |
-1 | 0 | 0 | 0 | 1 | 2 | 3 | 0 |
好,依据next数组我们就能确定目标串的回溯位置了,比如下面假设目标串和主串在索引为4的位置发生不匹配,所做的操作如下
KMP算法的思想大部分人是能很轻松的明白的,但是这个算法为什么劝退了很多人呢?就是无法准确,深刻的理解求解next数组的代码
void getnext(string target_str,int next[]){ int j=0,k=-1; next[0]=-1; while(j
你说它长也就算了,毕竟是一个具有难度的算法,但是它偏偏这么短,这就让人很尴尬。
上述代码中总共有三个地方如果能理解清楚这个代码也就没问题了。
next[0]=-1
,next[j]=l
,k=next[k]
,其中k=next[k]
最让人摸不着头脑 首先是next[0]=-1
,如下当目标串的第一个位置,也就是索引为0的位置,发生不匹配时,应该让目标串的索引为-1的位置与当前不匹配的地方对齐比较
j=next[j]
不用不说在干什么了,好的回到上面的问题,此时就是执行结果就是-1=next[0]
,也就是j=-1
了,然后重新回到循环,继续判断,此时j=-1
,进入if内,注意i++
,j++
,请问i++
是在干什么?,而j++
会等于0,这不就是让目标串的第一位与主串的下一位比较吗 所以你现在能理解为什么next[0]=-1
了吧
首先next[j]=k我认为大家肯定能明白的一点就是在为next数组进行位置,但是不明白的是为什么下标为j的元素的值是k
那么我想问哪种情况下会有next[j]=k
?,根据上面的代码自然是k=-1
或str[j]=str[k
]的时候。
好的现在,我们先考虑k=-1
,当k=-1
时,总会有k++
,使得k变为0
,这样的话next[j]=0
,表明前面没有相同的前后缀
那么一旦k不是-1,满足这个if的唯一条件就是str[j]=str[k]
了。如果此刻str[j]=str[k]
,这就表示此时的位置可以算作相同的前后缀了,我们所做的就是判断下一对了。
j++,k++,next[j]=3
我认为kmp算法的高潮部分就在这里!(为了方便说明,我换了一张图)
如下,j和k准备比较下一个很遗憾这个位置,无法使其成为长度为4的相同前后缀,那么根据代码只能执行k=next[k]了
这样画比较难受,我把前缀直接拿到下面来这就是为什么这样回溯的原因!
仔细想一想,下面的这种情况中已经不可能有ABAB,ABAC相等的情况存在了,因为一旦相同,那么next[9]=4了,也即是C之前不可能有长度为4的相同的前后缀,但是没有这么长的或许也有短的呀,你看咋们上面的那个AB=AB不就是一个短的情况吗,所以这也就是为什么有k=next[k]这样的回溯的情况。其实就是在前缀和后缀在比较,只不过一旦遇到不相等,前人栽树后人乘凉罢了!如果你能理解最后的那句谚语,那么这个算法你应该掌握的八九不离十了,这里也可以看出这个算法有多么的牛逼,简直即使巧妙之际,不得不佩服发明的这三位大牛的聪明才智啊
我觉得不用我再解释了吧
int KMP(string main_str,string target_str){ int next[MaxSize],i=0,j=0; getnext(target_str,next); while(i=target_str.size()) return i-target_str.size();//返回目标串在主串的第一个字符的位置 else return -1;//找不到返回-1}
转载地址:http://mjsi.baihongyu.com/