KMP算法用于在母串中查找子串的出现位置。
KMP算法:字符串匹配问题【有详细的引入过程,很容易理解掌握】
首先我们都知道,KMP算法的next数组可以指导匹配失败情况下,子串(模式串)的指针应该跳到哪里,而母串的指针是从来不会回头的。
假如在母串被跳跃过的部分中有个起点,恰好可以和子串匹配,那么我们不就错失正确答案了吗?
其实,这种情况是不会发生的,我们用的最长相同前后缀这个条件就限制了这种情况的发生。
下面用反证法来说明下:
如下的母串和子串,假设子串的最长相同前后缀是A这一部分(是一段,不是说一个字母A)。
在匹配到红叉时,发现匹配失败。
![](https://img-blog.csdnimg.cn/2020110520103244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxOTg5OTI3,size_16,color_FFFFFF,t_70)
按照我们的跳跃规则,我们可以直接跳过母串中间的空白部分,直接进行“?”处这一步的比较:
![](https://img-blog.csdnimg.cn/20201105202217947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxOTg5OTI3,size_16,color_FFFFFF,t_70)
质问的问题是:在母串的被跳跃的部分,是否可能存在一个我们漏掉的答案?如下图所示,粉色框内完全匹配,表示我们漏掉的答案。
![](https://img-blog.csdnimg.cn/20201107023550593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxOTg5OTI3,size_16,color_FFFFFF,t_70)
我们利用反证法来证明这种情况是不可能发生的。我们先假设上图所述情况真的存在。
因为粉色框内子串和母串相匹配,所以我们很容易在子串和母串中补全一些最长相同前后缀A。
补全后如下图所示,并且我们把母串两个A中间的部分称为B部分。
![](https://img-blog.csdnimg.cn/20201107022435868.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxOTg5OTI3,size_16,color_FFFFFF,t_70)
进一步补全图中的B部分。(此时我们把之前匹配成功的子串再挪回最开始的位置,方便我们找相同的量)
![](https://img-blog.csdnimg.cn/33be4b8452c545a0a1fb3a7f237b1dff.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ams5bCP6LaFaQ==,size_20,color_FFFFFF,t_70,g_se,x_16)
因为假设的子串和子串是同一个串,那么B在子串中一定存在(因为这里是匹配过的了),在假设的子串中也一定存在,同理 B之前的A部分也存在。
![](https://img-blog.csdnimg.cn/50ed364d91d5402589cbc285079051ed.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ams5bCP6LaFaQ==,size_20,color_FFFFFF,t_70,g_se,x_16)
此时我们发现母串和子串以及我们假设的子串中,都出现了ABA这个部分,由于子串和假设的子串是一个东西,所以我们可以最终发现,子串中有ABA部分的前缀和后缀,也就是他的最长相等前后缀并不是A,而是ABA。
![](https://img-blog.csdnimg.cn/b0260cb0d65d4e7a991a138a3aa4176a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ams5bCP6LaFaQ==,size_20,color_FFFFFF,t_70,g_se,x_16)
这跟我们的假设A是最长相同前后缀是不同的,所以可以说明,根本不存在这种情况。
结论:我们利用最长相同前后缀的条件,保证了每次子串的移动(也就是母串的被跳跃)是一定不会漏掉正确答案的。
到这里证明结束,其实KMP思想非常的简单,经过上面的讨论,如下图所示,匹配失败,你觉得再从哪里开始比较更合适?![](https://img-blog.csdnimg.cn/670ff403c8594ea195e69345d62e4f9e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6ams5bCP6LaFaQ==,size_20,color_FFFFFF,t_70,g_se,x_16)
你一定想说从子串的开头ABA和母串的适配的ABA,那这个ABA是个啥?
奥,是子串的最长相同前后缀。也就是我们辛辛苦苦求出来的next数组了。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)