（原创）KMP算法史上最详解，图文并用，Java实现，一篇文章带你搞懂KMP算法_kpm java

前言：前几天上网课学习KMP算法，玩手机去了，下来花了两天时间才算理解的差不多，于是打算写出来，希望能够对大家有一些帮助，话不多说，进入正题。

一.什么是KMP算法

1.1 KMP算法介绍

其实当你点进这篇文章的时候，我相信你是对kmp算法有一定了解的，至少清楚KMP算法是干什么的，不过还是容我介绍一下。
KMP算法是由三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt一起发现的。其中第一位就是《计算机程序设计艺术》的作者！！
KMP算法实现的功能是为了实现高效字符串匹配，提到这里就不得不鞭尸一下传统字符串匹配方法

对于传统方法，两个字符串从第一位开始比较，如果相等则进入下一位进行比较，

一旦比较失败也就是这样

i就会回到最开始的下一位然后再和下面的第一位比较，也就是这样

程序会一直这样比下去，一旦错误就回到开始比较的下一个，直到找到字符串或者主字符串查找完毕，这就是我们的传统方法。
可以看出这是一种最无脑，最暴力，最耗费时间的方法，我们都知道我们的大牛是最受不了这种方法的，于是他们仨在某一天就一起讨论有什么简便方法，于是就创造出了我们的KMP算法，不得不说大佬牛逼！
下面就是KMP算法的例子

如图,我们的字符串已经比较到了第五位，然后发生了错误，那么聪明的你不妨思考 i j 指针该如何移动呢，才是正确高效的呢

没错,相信你不难看出 i 指针应该保持不动，j 指针应该移动到图示位置,然后继续进行比较

相信你已经发现这了这么移动的好处，那么我来解释一下为什么这么移动。
我们的字符串是在第五位匹配失败的，这就意味着前面四位是完全匹配成功的，所以如果再把 i 指针移动回去，是一定会匹配失败的，所以我们就想着通过不移动 i 指针，直接移动 j 指针来进行字符串比较，从而实现字符串的高效查找，而这就是我们的KMP算法。

1.2 KMP算法与传统算法的区别

相信看到这里的你已经对KMP算法有了初步的理解，而KMP算法与传统算法的最大区别，就是当匹配失败发生时，KMP算法只需要移动 j 指针，就可以实现两个字符串继续匹配，而不需要让我们的 i 指针往回走，我们的 i 指针只会向前移动从而减少了大量的运算时间。

那么问题就来了，如何高效的移动 j 指针呢？

二. KMP算法的逻辑理解

2.1 KMP算法的实现过程

我们先来看这个图，和刚才一样，字符串再第五位匹配失败，此时不难看出 j 应该移动到图示位置。

我相信你一定发现其中有什么规律，只是你可能暂时说不出来，没关系，我们再看下面这张图

这张图，j 指针应该移动到图示位置，现在你明白其中的规律了吗？不明白也没关系，我来告诉你。

j 指针的移动规律就是，观察字符串匹配失败位置之前的字符串中是否有相同的前缀和后缀字符串，如果有，则 j 指针移动到前缀字符串下一位，如果没有，则 j 指针移动到第一位。
我知道上面那段话有点难以理解，没事我们看图说话。

此时我们再来看之前的P5，让我对他做些改变

再看P6

相信此时的你已经可以理解 j 指针移动规律的前半部分了，我们现在来看之前的P7

现在你应该明白 j 指针移动规律了吧，如果还没有呢，建议多看看上面几张图，自己在举一些例子来加深理解。

那么现在又出现了一个问题，那就是前后缀字符串如何确定呢？

2.2 next数组的逻辑理解

首先，我要告诉大家，关于前后缀字符串的确定，你需要明白以下几点：

1. 前后缀字符串是从之前的字符串中寻找，如你要确定第 j 位的最长前后缀位数，你是在前面 j-1 个字符中寻找
2. 前缀字符串从前面开始寻找，后缀字符串从后面开始寻找，但都是从前往后找(这里或许不好理解，之后看图就明白了)
3. 最长前后缀字符串位数一定小于等于 j-1
4. 我们假设字符从0开始
5. 前后缀字符串的寻找是针对模式串（要就是要寻找的字符串），与主字符串无关

如果对于以上几点还有些许疑惑，没事，我们看下面的例子。

对于字符串ABABDA，我们有如下表格

通过这张图，想必你应该明白了最长前后缀字符串的位数是如何寻找的了,现在我们把所有位数放在相应的位置上，变成这样

这张图应该会直观，对于字符串ABABDA,每个字符下的数字都是其前后缀相同字符串的最长位数。

那么这张表格有什么用处呢？当然是引出我们的next数组啦

现在让我们来学习next数组

首先，我们先来看对于模式串ABABDA的next数组是什么样的

仔细观察P10和P9，相信你已经发现了对于模式串ABABDA，其 next数组的值与其前后相同最长字符串位数表基本相同，除了第一位从0变成了-1，这是有原因的，不过这里暂且不说，等等告诉你。

我知道你一定会好奇，这个next数组有什么用，我告诉你

next数组是计算机实现KMP算法的核心

你仔细思考一下，我们是如何判断 j 指针的移动的呢？

你会告诉我，根据 j 指针移动规律，我们要先看j 位置之前的模式串中是否有相同的前后缀字符串，如果有则移动到前缀字符串的下一位，如果没有，则移动到第一位。

很好，你已经掌握了之前的知识，不过这不是上面那个问题的答案，问题的答案是用眼睛看！

没错，在明白 j 指针移动规律后，我们一眼就可以看出 j 指针的移动位置，可是计算机如何实现呢？计算机又不长眼睛，对吧，所以我们需要next数组来告诉它 j 指针该如何移动。

请看这张图

根据P11，主串与模式串在第四个位置匹配失败（从0开始算），按照我们的眼睛来看，j 指针应该移动到红色指针处，可是计算机是如何将 j 指针移动过去的呢？我已经写在那里了 j= next[ j ], 这样我们的 j 指针就从4移动到了2，也就是前缀相同字符串的下一位。

我知道你一定在想，为什么 j =next[j] 就可以把 j 指针移动到正确的位置呢？

因为next数组的值，如 next[ j ]=k,其含义就是第 j 个字符前，共有k个字符相同前后缀串，通过
j =next [ j ],我们直接将 j 指针移动到前缀字符串的下一位，通过图片你也可以理解为将前缀字符串移动到后缀字符串的，这样我们就实现了高速匹配

如果我没记错的话，我之前答应过你，要告诉你为什么next [0]要变成-1而不是我们自己认为的0吧，现在是时候了。

我们看这张图

对于P12，我们可以看到主串与模式串第一个位置都不相等，这时候如何移动 j 指针都不管用，正确的做法是让 i 指针向前移动一位，和 j 指针进行比较。

可计算机是如何实现的呢？ 很简单还是 j=next[j],也就是 j=next[0]=-1,此时 j 等于-1，可是 i 是不能与 j
进行比较的，因为Java数组索引里没有-1，所以主字符串就明白了，哦，我该往前走一位了，于是 i=i+1。
没错，next[0]=-1,就是为了告诉主串，我俩第一个都对不上，你的 i 该往前了，就这个意思，相当于一种特殊情况。

好的，到目前为止，你已经明白了next数组的作用与逻辑上的求法，是时候讲代码了！

三. KMP算法的代码实现

3.1 next数组的代码实现

首先我们先拿出next数组的代码

```java
//得到next数组
	public static int [] getNext(String ps) {
		
		char [] p =ps.toCharArray();        //将字符串变成对应的char[]数组
		int [] next = new int [p.length];	//生成同长度的next数组
		next[0]=-1;							//让next[0]=-1,这是我们的特殊情况
		int j =0;                           //后缀字符串的最后一位，没有相同字符串时，就是第一位
		int k=-1;      						//前缀字符串的最后一位，没有相同字符串时，就是第一位					
		while(j<p.length-1) {               //只用遍历到倒数第二位即可推出最后一位的next值，记住我之前说的求 j位的前后缀相同字符串位数
											//（也就是next[j]）,只需看前j-1位
			
			if(k==-1||p[j]==p[k]) {         //判断条件
				next[++j]=++k;
			}
			else {
				k=next[k];
			}
		}
		return next;	
	}
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在讲解next数组代码之前，我希望你记住next数组值的核心含义，也就是下面这句三句真言

next[ j ] = k 的意思是，当第 j 个位置匹配失败时，指针应该移动到 k 的位置
next[ j ] = k 的意思是，第 j 个位置之前共 j-1 个字符中，一共有k个字符相等
指针k永远是相同前后缀中前缀的最后一位，指针 j 永远是后缀的最后一位

如果你对前两句话还不理解，建议看图P11,一定要理解。第三句话之后你就明白了。
一旦你在接下来的代码学习中出现任何问题，请背诵并思考上面的话

现在开始讲解代码，简单的就不说了，代码里的注释都有，直接从while()循环开始

while循环里的语句就是具体的求next值的过程，

现在请让我们开始第一遍循环（这是比较特殊的一环，需要单独提出来讲解）

但第一重循环并不难，就是因为k==-1，于是
next[++j]=++k;
即next[1]=0,j=1,k=0这是显而易见的，因为第1位前面不可能有 相同的字符串。

现在开始进入一般情况，我们从if语句的判定入手

3.1.1 现在我们来看if语句生效的第二种情况，p [ j ]==p [ k ]

我们为什么说这种情况是第一种可能呢，就是因为此时p[j]第一次等于p[k],之前p[j] 一直不等于p[k]

当p[j]=p[k]后，j和k都会加加，也就是移动到下一位

现在我们看第二种情况

我们说这是第二种情况，什么情况呢，那就是p[j]=p[k]不是第一次发生，也就是之前已经发生过，这意味着什么呢，意味着
next[ j+1]=next[j]+1,这句话和代码里的next[++j]=++k,其实是一个意思，为什么呢，因为next[j]的值其实就是k，不明看第二句真言

如果还不明白，我们看下面这张图

所以p[k]和p[j]会一直这样比较下去，next[j+1]的值永远等于next[j]+1,直到模式串结束，或者p[j]!=p[k]

现在你应该可以明白next[j+1]=next[j]+1的含义了吧。

3.1.2 现在，我们来看else语句发生的情况

else语句执行的情况就是p[j]!=p[k]且k！=-1，这意味什么呢？

我们来看着张图

这是我从别人博客里复制的图，稍后我会把链接放在下面

我们看此时p[j]和p[k]不相等，这就意味着，我们找不到k+1（注意k=3）个字符相等，所以我们就想着，可不可以，找长度更小的，比如3个字符，2个字符，1个字符，这里我们很幸运找到了，也就是ABA.

那么计算机是如何实现的呢？我们看代码发现是k=next[k],心细的你有没有发现这个代码很眼熟啊，我们之前讲计算机如何通过next[ ]数组来移动 j 指针时，有一个代码是 j= next[j]

对，没错，这里的原理和 j=next[j]的原理是相同的，只不过主串变成了ABABC,模式串变成了ABAC,忘记了的同学，可以往上翻，再看看P11，就可以回想起来了

k=next[k] 原理与 j=next[j] 原理相同，只不过换成了后缀模式串与前缀模式串匹配失败时，前缀模式串 指针 k 的移动位置，目的是找到长度更短的相同前后缀模式串

这张图同样出自那个博客，看了这张图，你有没有明白呢？

3.1.3 现在我们来看if语句生效的第一种情况，也就是k==-1

我之所以现在打乱顺序，最后才来讲这种情况，当然是因为放在后面，有了前面的铺垫，你就可以很轻松的理解这段代码了，为什么要这么写啊?

很简单，因为我们刚才说了当p[j]!=p[k]的时候，我们的k会等于next[k],也就是我们找不到k+1个字符相等，我们就尝试着找k-1，k-2，k-3，一直到1个字符相等，如果这些都找不到，最后会怎样啊?

最后是不是就变成了 k=next[0]=-1,此时k变成-1 就意味着告诉next[j+1]，别找了，你前面一个相等的字符都没有，你直接等于0吧，等于0怎么实现的啊，就是k==-1时，next[++j]=++k，k从-1变成0实现的。

花了这么大的篇幅，我们总算是学习完next数组的代码实现了，如果你还有疑惑，很正常，多思考就完事了，谁也不能看一遍就懂啊！。

3.2 KMP算法的代码实现

这里的KMP算法代码是指除掉next数组代码，剩下的那部分，直接看代码吧！

public static int KMP(String ts,String ps) {   //ts是主串，ps是模式串
		char [] t =ts.toCharArray();  
		char [] p =ps.toCharArray();          // 两个字符串变成数组方便比较
		int [] next =getNext(ps);            //调用方法得到模式串的next数组
		int i=0;      //主串的位置
		int j=0;	 //模式串的位置
		while(i<t.length&&j<p.length) {
			if(j==-1||t[i]==p[j]) {
				i++;
				j++;
			}
			else {
				j=next[j];
			}
		}
		if(j==p.length) {          //匹配到了
			return i-j;
		}
		else {
			return -1;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

其实我相信之前认真学习的同学已经能看明白这个代码了，不过我还是有始有终吧。

3.2.1while循环

我们看到while循环条件就是

while(i<t.length&&j<p.length)
1

很好理解，i j 是两个字符串的指针，一旦跳出循环，就以为着二者至少有一个等于了对应数组的长度，也就是此时匹配已经结束了。

那么什么时候算是查找成功了呢？自然是我们的 j 指针等于p数组长度的时候，这意味着p数组已经被比较完毕了，所以 j 才等于数组长度，此时就该返回模式串在主串的位置也就是

if(j==p.length) {          //匹配到了
			return i-j;   //在已经被遍历的长度中，减去p数组的长度，
							//自然就是开始位置了
		}
1
2
3
4

我们再看while循环结构里的 if else 结构

if(j==-1||t[i]==p[j]) {
	i++;
	j++;
}
else {
	j=next[j];
}
1
2
3
4
5
6
7

如果你已经明白了我之前所讲的 j 指针移动规律，那么现在应该很用以看懂这串代码，如果t[ i ]==p[ j ]，表示两个字符匹配成功，于是两个指针向下移懂再次匹配，知道匹配失败或者匹配结束

如果匹配失败则 j=next[ j ]，j指针移动位置，然后再次匹配，如果还匹配失败，j指针继续移动，如此循环，直到 j=-1，于是我们的主串就明白了，我该前进一位了，当然 j 也得加一归零，于是新一轮的匹配又开始了。

好了，到了这里我们的KMP算法总算是讲解完毕了，希望对你有所帮助

结语

我个人认为呢，KMP算法，最难理解的就是next数组的代码实现了，如果你还有什么不明白的，你可以多多思考，再看看没懂的部分。

这就是我之前说的那篇文章，写的蛮好的，也可以看看，开拓一下思路
另一篇KMP算法教程

作者：渝州少年
本文为作者原创，转载请注明出处！！！
https://editor.csdn.net/md?articleId=105344118