KMP算法图文解析

又过了好久,正好这几天在复习软考的时候遇到了一个难题,kmp算法,第一次听到这个算法的时候我也是很懵,从来没听说过,现在我们就来具体,了解一下

kmp算法解决的问题

思考一个问题,如何从下面这个字符串中找出字串(目标串)
image-20221015211211607

相信大家想到的第一个解决方法就是暴力破解——用两个指针,开始时分别指向两个串的开头,然后比较,如果相同继续扫描下一个字符,一旦出现不相同,两个指针进行回溯,主串的指针回溯到下一位,目标串的指针回溯至第一位,然后继续按照上述步骤比较,如下图

-注意:回溯的步骤在图中表示为了目标串向后移动的,但是实际物理内存中字符串是不可能移动的,这里只是为了形象解释

这样的话你就可以按照这个思想写出相关的代码

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

为了便于介绍,我将主串和目标串设置为这样

  • 当然,下面的例子中目标串并未出现在主串中,但不要紧,这里只是为了说明更好的说明

image-20221015212439106

暴力匹配的缺点

通过上面的叙述,大家可能已经发现了暴力匹配的缺陷所在——回溯太过频繁了。只要出现不匹配就需要回溯到下一位

image-20221015212524749

这样无脑回溯其实并不合理,比如下面这种情况中,如果让你进行回溯的话,你肯定不会直接回溯到下一位,起码也得是下面这样吧

  • 这是因为你明白直接回溯到下一位会导致连第一位都不会匹配,就更别谈后面了

image-20221015212624318

所以KMP的算法的核心点就在这里:不要回溯到无效的地方,让其回溯到有效的位置

最长相同前缀和后缀

在继续讲述之前,必须引入一个概念——一个字符串的最长相同前缀和后缀。要想知道什么是最长相同前缀和后缀,首先得明白什么是字符串的前缀和后缀,相信看完下面这个图你就不难理解了

image-20221015212757935

那么,最长相同前缀和后缀你也应该能找出来了吧

  • 什么?竟然不是最下面的那个吗?这里就要给大家说明一点,最长相同前后缀不能是字符串本身,因为如果你认为最长相同前后缀可以是字符串本身的话,那么这就是一个恒成立的命题了,那么再继续讨论就没有意义了

image-20221015212842367

究竟怎么回溯

继续使用上面那个“你认为应该这样回溯”的例子

image-20221015212919398

仔细观察你会发现它回溯的位置有些特点?没错,就是最长公共前后缀重合的地方,也就是说让最长相同前缀对齐至后缀

不仅仅是这样,继续观察,目标串发生不匹配时其索引为5,索引5之前的字符串为“ABCAB”,其最长相同前后缀长度为2,同时目标串中也正好是索引为2的地方(也即字母C)与主串发生不匹配的地方(也即字母E)对齐

这意味着所谓让最长相同前缀对齐至后缀其本质就是:记目标串发生不匹配的地方前的字符串的最长相同前后缀长度为l ll,然后回溯时让目标串索引为l ll的地方对齐至此次不匹配的地方

这里我们可以再举几个例子
①:如下目标串的索引为3号的位置发生不匹配

image-20221015215757903

其3号位置前的字符串的最长相同前后缀的长度是1,所以就应该让目标串索引为1的位置与该不匹配处“对齐”

image-20221015215817411

②:如下目标串的索引为5号的位置发生不匹配

image-20221015213601863

其5号位置前的字符串的最长相同前后缀的长度是2,所以就应该让目标串索引为2的位置与该不匹配处“对齐”

image-20221015213640961

讲到这里,大家可能也应该意识到了,这意味着匹配时根本就“不需要”主串,因为每个位置发生不匹配时,总有一个值能确定其应该回溯的位置。这个值就是其前面的字符串的最长相同前后缀的长度

next数组

我们把目标串每个位置发生不匹配时,目标串应该回溯的位置给记录下来,形成一个数组,这个数组就是所谓的next数组。next[i]=j,就表示索引为i的位置发生不匹配,就让其回溯到j的位置继续匹配

next数组的计算方法我其实前面已经说到过了,如下目标的串next数组计算如下,需要注意是由于第一个位置也就是next[0]前面没有串,所以记为-1

image-20221015213900388

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的位置发生不匹配,所做的操作如下

image-20221015214059439

求解next数组

KMP算法的思想大部分人是能很轻松的明白的,但是这个算法为什么劝退了很多人呢?就是无法准确,深刻的理解求解next数组的代码,如下

  • 上述代码中总共有三个地方如果能理解清楚这个代码也就没问题了。
    next[0]=-1,next[j]=l,k=next[k],其中k=next[k]最让人摸不着头脑
void getnext(string target_str,int next[])
{
	int j=0,k=-1;
	next[0]=-1;
	while(j<target_str.size())
	{
		if(k==-1 || str[j]==str[k])
		{
			j++;
			k++;
			next[j]=k;
		}
		else
		{
			k=next[k];
		}
	}
}

A:next[0]=-1

如下,next[0]=-1是指当目标串的第一个位置发生不匹配时,应该让目标串的索引为-1的位置与当前不匹配的地方对齐

  • 你肯定会问,怎么可能有-1的位置啊,这明显越界了啊?

image-20221015214315679

这里我们先截取KMP算法的一小段(不要担心你肯定看得懂)

  • 下面的j=next[j]指的就是发生不匹配时应该如何回溯

image-20221015214354365

因此当代码运行到这里时就会出现j=next[0]=-1,然后重新回到循环,继续判断,此时j=-1,进入if内,j++很明显会等于0,i++会到主串的下一位。所以它的意思就是让目标串的第一位与主串的下一位进行比较

  • 现在你应该能理解为什么要设置next[0]=-1了吧

B:next[j]=k

对于next[j]=k我认为大家肯定能明白的一点就是在为next数组进行赋值,但是不明白的是为什么下标为j的元素的值是k
首先请大家考虑哪种情况下会有next[j]=k?根据上面的代码自然是k=-1或str[j]=str[k]的时候

当k=-1时,总会有k++,使得k变为0,这样的话next[j]=0,表明前面没有相同的前后缀

一旦k不是-1,满足这个if的唯一条件就是str[j]=str[k]了。如果此时str[j]=str[k],这就表示此时的位置可以算作相同的前后缀了,我们所做的就是判断下一位了

比如下面,可以看出,此时k来到了C的位置,j也来到了C的位置,他们之前都各自在B的位置,由于相同,所以来到了现在位置,现在他们要判断此刻对应的位置是否可以也将其算入相同的前后缀

image-20221015214728237

非常幸运,他们相同,于是j++,k++,next[j]=3

image-20221015214809948

C:k=next[k]

  • KMP算法最难理解的地方就在这里,为了方便说明,我换了一张图

如下,jk准备比较下一个

image-20221015214905801

image-20221015215148873

有没有似曾相识的感觉?没错,好像是主串和目标串,但这不是原来的那个两个串。而是后缀作为了主串,前缀作为了目标串,好的,现在前缀(目标串)的索引为3的位置发生了不匹配,该怎么做?自然是让前缀(目标串)下标为1的位置(next[3]=1)与该不匹配处重新比较

image-20221015215216377

好的,重新组装回去,毕竟这不是真的主串和目标串

image-20221015215245307

现在if继续判断,当然满足,对应位置相同,那么继续i++,j++,于是next[9]=2,此时next数组全部赋值完成。

仔细想一想,下面的这种情况中已经不可能有ABAB,ABAC相等的情况存在了,因为一旦相同,那么next[9]=4了,也即是C之前不可能有长度为4的相同的前后缀,但是没有这么长的或许也有短的呀,你看咋们上面的那个AB=AB不就是一个短的情况吗,所以这也就是为什么有k=next[k]这样的回溯的情况。其实就是在前缀和后缀在比较,只不过一旦遇到不相等,前人栽树后人乘凉罢了!——其实这本质是动态规划

image-20221015215314519

KMP算法代码

我觉得不用我再解释了吧

int KMP(string main_str,string target_str)
{
	int next[MaxSize],i=0,j=0;
	getnext(target_str,next);
	while(i<main_str.size() && j<target_str.size())
	{
		if(j==-1 || main_str[i]==target_str[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j>=target_str.size())
		return i-target_str.size();//返回目标串在主串的第一个字符的位置
	else
		return -1;//找不到返回-1

}