KMP 算法 C++版讲解

逃离我推掉我的手 2022-02-23 08:26 300阅读 0赞

大佬Java版精彩讲解：[https://www.cnblogs.com/yjiyjige/p/3263858.html][https_www.cnblogs.com_yjiyjige_p_3263858.html]

KMP算法应该是每一本《数据结构》书都会讲的，算是知名度最高的算法之一了，但很可惜，我大二那年压根就没看懂过~~~

之后也在很多地方也都经常看到讲解KMP算法的文章，看久了好像也知道是怎么一回事，但总感觉有些地方自己还是没有完全懂明白。这两天花了点时间总结一下，有点小体会，我希望可以通过我自己的语言来把这个算法的一些细节梳理清楚，也算是考验一下自己有真正理解这个算法。

**什么是****KMP****算法：**

KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者！！

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。

![17083616-9b40c67ea22e449f813fb38fcfd3a4fb.png][]

首先，对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？

我们可以这样初始化：

![17083647-9dfd3e4a709c40dd98d9817927651960.png][]

之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：

![17083659-e6718026bf4f48a0be2d5d6076be4c55.png][]

A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：

![17083714-7de56d2c1cc84dbfa376cf410ba6f053.png][]

基于这个想法我们可以得到暴力程序

但不够好！（想起我高中时候数字老师的一句话：我不能说你错，只能说你不对~~~）

如果是人为来寻找的话，肯定不会再把i移动回第1位，**因为主串匹配失败的位置前面除了第一个****A****之外再也没有A****了**，我们为什么能知道主串前面只有一个A？**因为我们已经知道前面三个字符都是匹配的！（这很重要）**。移动过去肯定也是不匹配的！有一个想法，**i****可以不动，我们只需要移动j**即可，如下图：

![17083828-cdb207f5460f4645982171e58571a741.png][]

上面的这种情况还是比较理想的情况，我们最多也就多比较了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”，比较到最后一个才知道不匹配，然后i回溯，这个的效率是显然是最低的。

大牛们是无法忍受“暴力破解”这种低效的手段的，于是他们三个研究出了KMP算法。其思想就如同我们上边所看到的一样：“**利用已经部分匹配这个有效信息，保持****i****指针不回溯，通过修改j****指针，让模式串尽量地移动到有效的位置**。”

所以，整个KMP的重点就在于**当某一个字符与主串不匹配时，我们应该知道****j****指针要移动到哪**？

接下来我们自己来发现j的移动规律：

![17083912-49365b7e67cd4877b2f501074dae68d2.png][]

如图：C和D不匹配了，我们要把j移动到哪？显然是第1位。为什么？因为前面有一个A相同啊：

![17083929-a9ccfb08833e4cf1a42c30f05608f8f5.png][]

如下图也是一样的情况：

![17084030-82e4b71b85a440c5a636d57503931415.png][]

可以把j指针移动到第2位，因为前面有两个字母是一样的：

![17084037-cc3c34200809414e9421c316ceba2cda.png][]

至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：**最前面的****k****个字符和j****之前的最后k****个字符是一样的**。

如果用数学公式来表示是这样的

P\[0 ~ k-1\] == P\[j-k ~ j-1\]

这个相当重要，如果觉得不好记的话，可以通过下图来理解：

![17084056-66930855432b4357bafbf8d6c76c1840.png][]

弄明白了这个就应该可能明白为什么可以直接将j移动到k位置了。

因为:

当T\[i\] != P\[j\]时

有T\[i-j ~ i-1\] == P\[0 ~ j-1\]

由P\[0 ~ k-1\] == P\[j-k ~ j-1\]

必然：T\[i-k ~ i-1\] == P\[0 ~ k-1\]

公式很无聊，能看明白就行了，不需要记住。

这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。

好，接下来就是重点了，怎么求这个（这些）k呢？因为在P的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，**next\[j\] = k****，表示当T\[i\] != P\[j\]****时，j****指针的下一个位置。**

很多教材或博文在这个地方都是讲得比较含糊或是根本就一笔带过，甚至就是贴一段代码上来，为什么是这样求？怎么可以这样求？根本就没有说清楚。而这里恰恰是整个算法最关键的地方。

int next[100];
    string T,t;
    void getnext(){
    	int n=t.size();
    	next[0]=-1;
    	int j=0,k=-1;
    	while(j<n)
    		if(k==-1||p[k]==p[j])next[++j]=++k;//等于上一个相同字符的位置 
    		else k=next[k];//k等于之前的  直到k==-1 
    }

这个版本的求next数组的算法应该是流传最广泛的，代码是很简洁。可是真的很让人摸不到头脑，它这样计算的依据到底是什么？

好，先把这个放一边，我们自己来推导思路，现在要始终记住一点，**next\[j\]****的值（也就是k）表示，当P\[j\] != T\[i\]****时，j****指针的下一步移动位置**。

先来看第一个：当j为0时，如果这时候不匹配，怎么办？

![17084258-efd2e95d3644427ebc0304ed3d7adefb.png][]

像上图这种情况，**j****已经在最左边了，不可能再移动了，这时候要应该是i****指针后移**。所以在代码中才会有next\[0\] = -1;这个初始化。

如果是当j为1的时候呢？

![17084310-29f9f8dbb6034151a383e7ccf6f5583e.png][]

显然，**j****指针一定是后移到0****位置的**。因为它前面也就只有这一个位置了~~~

下面这个是最重要的，请看如下图：

![17084327-8a3cdfab03094bfa9e5cace26796cae5.png][] ![17084342-616036472ab546c082aa991004bb0034.png][]

请仔细对比这两个图。

我们发现一个规律：

当P\[k\] == P\[j\]时，

有next\[j+1\] == next\[j\] + 1

其实这个是可以证明的：

因为在P\[j\]之前已经有P\[0 ~ k-1\] == p\[j-k ~ j-1\]。（next\[j\] == k）

这时候现有P\[k\] == P\[j\]，我们是不是可以得到P\[0 ~ k-1\] + P\[k\] == p\[j-k ~ j-1\] + P\[j\]。

即：P\[0 ~ k\] == P\[j-k ~ j\]，即next\[j+1\] == k + 1 == next\[j\] + 1。

这里的公式不是很好懂，还是看图会容易理解些。

那如果P\[k\] != P\[j\]呢？比如下图所示：

![17122358-fd7e52dd382c4268a8ff52b85bff465d.png][]

像这种情况，如果你从代码上看应该是这一句：k = next\[k\];为什么是这样子？你看下面应该就明白了。

![17122439-e349fed25e974e7886a27d18871ae48a.png][]

现在你应该知道为什么要k = next\[k\]了吧！像上边的例子，我们已经不可能找到\[ A，B，A，B \]这个最长的后缀串了，但我们还是可能找到\[ A，B \]、\[ B \]这样的前缀串的。所以这个过程像不像在定位\[ A，B，A，C \]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next\[k\]啦。

有了next数组之后就一切好办了，我们可以动手写KMP算法了：

#include<bits/stdc++.h>
    using namespace std;
    int next[100];
    string T,t;
    void getnext(){
    	int n=t.size();
    	next[0]=-1;
    	int j=0,k=-1;
    	while(j<n)
    		if(k==-1||p[k]==p[j])next[++j]=++k;//等于上一个相同字符的位置 
    		else k=next[k];//k等于之前的  直到k==-1 
    }
    int solved(){
    	int i=0,j=0,n=T.size(),m=t.size();
    	while(i<n&&j<m){
    		if(j==-1||T[i]==t[j]){//如果 j是-1(说明子串第一个字符匹配失败) 或者 如果匹配成功   
    			i++;j++; 
    		}else	j=next[j];//向前 
    	}//如果匹配成功   或者所有的都比较过了却不成功  退出循环 
    	if(j==m)return i-j;
    	return -1;
    } 
    int main(){
    	cin>>T>>t;
    }

[https_www.cnblogs.com_yjiyjige_p_3263858.html]: https://www.cnblogs.com/yjiyjige/p/3263858.html
[17083616-9b40c67ea22e449f813fb38fcfd3a4fb.png]: /images/20220223/73b124fc5f3b408f9d9b1ff397d1b883.png
[17083647-9dfd3e4a709c40dd98d9817927651960.png]: /images/20220223/9b63937326a5420a9b46dcae234d238a.png
[17083659-e6718026bf4f48a0be2d5d6076be4c55.png]: /images/20220223/f662aeaa07474a55aa987010c2f2d193.png
[17083714-7de56d2c1cc84dbfa376cf410ba6f053.png]: /images/20220223/d7cd8415c4da4196ab58719f1ba7bf01.png
[17083828-cdb207f5460f4645982171e58571a741.png]: /images/20220223/d6e2335e94754b47b5643142cad24a49.png
[17083912-49365b7e67cd4877b2f501074dae68d2.png]: /images/20220223/88f116163d134740886abec0d6419108.png
[17083929-a9ccfb08833e4cf1a42c30f05608f8f5.png]: /images/20220223/eaeafa152459403ca0b0ce5730e35b58.png
[17084030-82e4b71b85a440c5a636d57503931415.png]: /images/20220223/9bfebe4764cd4f79a62334ba0dacae5e.png
[17084037-cc3c34200809414e9421c316ceba2cda.png]: /images/20220223/e9f805e1a5dc44048ac5bb2beda16d6c.png
[17084056-66930855432b4357bafbf8d6c76c1840.png]: /images/20220223/53c7e5b7bd0b49a4b41e17cb8018f6dd.png
[17084258-efd2e95d3644427ebc0304ed3d7adefb.png]: /images/20220223/11aab3c7e4ca4db6b4f5da495a1fb636.png
[17084310-29f9f8dbb6034151a383e7ccf6f5583e.png]: /images/20220223/5971b802a06c40699e9c5e0ee1dd94c3.png
[17084327-8a3cdfab03094bfa9e5cace26796cae5.png]: https://images0.cnblogs.com/blog/416010/201308/17084327-8a3cdfab03094bfa9e5cace26796cae5.png
[17084342-616036472ab546c082aa991004bb0034.png]: /images/20220223/8482641947804c4abe973b2796bc13f3.png
[17122358-fd7e52dd382c4268a8ff52b85bff465d.png]: /images/20220223/788b26f9b88146e29a268ad3752c6724.png
[17122439-e349fed25e974e7886a27d18871ae48a.png]: /images/20220223/0573a8ee11ac4b398fd3ed94d32fe8c0.png