最容易理解,又很核心的思路,KMP算法为什么可以不比较中间元素?

首先,要明白下面这段简单的话:

判断一个事物A不等于事物B有两种方法:

1、直接比较A和B的差别(我们经常这么做,比如我们观测到葫芦娃和穿山甲,才知道他们是两种不同的东西,但重点在下面)

2、知道A等于【不是B的东西】,就能判断A不等于B(比如我们知道某个东西一定是人类,那么我们肯定这个东西一定不是穿山甲)

 

套入我们的KMP算法:

最容易理解,又很核心的思路,KMP算法为什么可以不比较中间元素?

 

因为【路人元素】==【不是前缀的东西】

所以【前缀】不等于【路人元素】

所以为了匹配到下个子串,【前缀】也不用比较【路人元素】了,直接跳过就行了。 

 

--------------

理解了上面之后,为了以后迅速想起算法的本质,

可以再进一步抽象为【子串“中间”的元素【帮助】前缀进行了比较】

这里中间的元素指的就是【不是前缀的东西】

 

----------------

不管前缀长度是多少,这个规则都是适用的。