[数据结构与算法]数据结构KMP算法配图详解（超详细）

一、什么是KMP算法？

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法是在 BF 算法基础上改进得到的算法。学习 BF 算法我们知道，该算法的实现过程就是 “傻瓜式” 地用模式串（假定为子串的串）与主串中的字符一一匹配，匹配不成功则返回到上一次与主串匹配的下一位字符进行匹配，算法执行效率不高。

二、KMP算法的解决题型

KMP算法是在数据结构中两个字符串相互匹配衍生出来的算法。KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。例如，对主串 A（“ABCABCE”）和模式串 B（“ABCE”）进行模式匹配，如果人为去判断，仅需匹配两次。虽然在以上字符较少的串中人为匹配很容易，但是让计算机来匹配就相对慢一些，但是当字符串中的字符非常多的时候，就不可能人为去匹配。所以打铁还需自身硬，我们把这种枯燥的事以一定的算法交给计算机处理。

图1：

第一次如图 1 所示，最终匹配失败。但在本次匹配过程中，我们可以获得一些信息，模式串中 “ABC” 都和主串对应的字符相同，但模式串中字符 ‘A’ 与 ‘B’ 和 ‘C’ 不同。

因此进行下次模式匹配时，没有必要让串 B 中的 ‘A’ 与主串中第一次匹配的字符 ‘B’ 和 ‘C’ 一一匹配（它们绝不可能相同），而是直接去匹配失败位置处的字符 ‘A’ ，如图二所示。

图2：

至此，匹配成功。若使用 BF 算法，则此模式匹配过程需要进行 4 次。

由此可以看出，每次匹配失败后模式串移动的距离不一定是 1，某些情况下一次可移动多个位置，这个位置是不确定的，因此这个不确定的移动位置就是KMP算法的难点与重点，这就是 KMP 模式匹配算法。

三、模式串移动距离的判断（next数组）

每次模式匹配失败后，计算模式串向后移动的距离是 KMP 算法中的核心部分。

其实，匹配失败后模式串移动的距离和主串没有关系，只与模式串本身有关系。

例如，我们将前面的模式串 B 改为 “ABCAE”，则在第一次模式匹配失败，由于匹配失败位置模式串中字符 ‘E’ 前面有两个字符 ‘A’，因此，第二次模式匹配应改为图三所示的位置：

图三：

结合图 1、图 2 和图 3 不难看出，模式串移动的距离只和自身有关系，和主串无关。换句话说，不论主串如何变换，只要给定模式串，则匹配失败后移动的距离就已经确定了。

不仅如此，模式串中任何一个字符都可能导致匹配失败，因此串中每个字符都应该对应一个数字，用来表示匹配失败后模式串移动的距离。

因此，我们可以给每个模式串配备一个数组（例如 next[]），用于存储模式串中每个字符对应指针 j 重定向的位置（也就是存储模式串的数组下标）。

模式串中各字符对应 next 值的计算方式是，取该字符前面的字符串（不包含自己），其前缀字符串和后缀字符串相同字符的最大个数就是该字符对应的 next 值。

前缀字符串指的是位于模式串起始位置的字符串，例如模式串 “ABCD”，则 “A”、“AB”、“ABC” 以及 “ABCD” 都属于前缀字符串；后缀字符串指的是位于串结尾处的字符串，还拿模式串 “ABCD” 来说，“D”、“CD”、“BCD” 和 “ABCD” 为后缀字符串。简单地来说，next数组的计算方式就是指不包含将要进行匹配的字符的前一个字符为后缀，而取模式串中第一个字符为首的字符串作为前缀，并计算模式串中第一个字符作为前缀、将要比较的字符的上一个字符作为后缀的两个相同的串长度就是将要进行匹配的字符的next[下标]值，没有相同的则next值为0。next的值作为匹配不成功后下一次匹配将要回溯的模式串的下标。

注意，模式串中第一个字符对应的值为 -1，第二个字符对应 0 ，这是固定不变的。因此，图 3 的模式串 “ABCAE” 中，各字符对应的 next 值如图4所示：

图四：

因为从前往后第一个字符’A’与字符’B’的next值已经确定，而字符‘C’的前面只有字符’A’与字符’B’，没有相同的串则为0；再向后，将要进行匹配的字符’A’的前面有字符’A’、字符’B’、字符’C’，没有以前缀为A，后缀为C的两个字符串，因此该字符’A’的next值为0；再向后，将要匹配的是’E’字符，而‘E’字符前面有以字符’A’为前缀，以字符’A’为后缀的字符串，正是字符串’A’，其长度为1（一个字符在此处用一个串来表示），则字符‘E’的的next值为1。

以上所讲 next 数组的实现方式是为了让大家对此数组的功能有一个初步的认识。接下来学习如何用编程的思想实现 next 数组。编程实现 next 数组要解决的主要问题依然是 “如何计算每个字符前面前缀字符串和后缀字符串相同的个数”。

以下有三种求得next数组的情形。

情形一：
图五：

我们观察图五，前提条件有next[i]=k与p[i]=p[k]，假设模式串为p，可以观察到有这样的规律：式子一：p[0]...p[k-1]=p[x]...p[i-1] （第一个出现的串abc与i下标前面的一个串abc内容相等） ，因此x是模式串p中的某一个下标。有此规律后，可以衍生为k-1-0==i-1-x，最后求得x=i-k 。将x=i-k代回到式子一当中，有式子二：p[0]...p[k-1]=p[i-k]...p[i-1]。因为有前提p[i]=p[k]，则将p[i-1]改为p[i]，p[k-1]改为p[k]，因此又能运算得到式子三：p[0]...p[k]=p[i-k]...p[i]。因为有式子三与前提条件next[i]=k，则能推出next[i+1]=k+1 （next数组在任何情况下都要成立此条件）。

图六：

情形二：
图七：

此时不满足p[i]=p[k]（任何时候都令next[i]=k），那么这种情形下如何求得next数组的下标呢？如果对情形一理解了，理解情形二就会简单很多。如果p[i]!=p[k]，则以图七举例，第一次匹配不成功，模式串p回退到下标为2的位置，但是下标为2的位置的字符开始就不一定是要找的字符。此时就需要继续回退，回退到了下标0，即第一个字符‘a’，这时我们发现居然再次满足了next[i+1]=k+1。

当然还有一种特殊情况，只是单纯举例求得next数组，也就是当我们如果回溯到第一个字符时仍然不相同，此时到达的是下标为-1的字符中，但是我们的数组中是不存在下标为-1的。因此回溯到下标为0的就无法再回溯了，只能从模式串p的第一个字符开始重新匹配。

注意：

1. next数组的值每次只能加1，不能跳着加，否则一定是错的。
2. 当确定将要确定某个字符对应的next的值并且与它的下标为k的字符不相同时，将要确定某个字符的next值不一定要从0开始。
3. 用编程来实现next数组需要注意的是我们不知道第i的next值为多少，但是我们知道只要有p[i]=p[k]，则必定有next[i+1]=k。因此我们要从前往后推。只在next数组的下标为0的值放入-1，其他的next值都进行“知前往后”推导。

这里给出使用上述思想实现 next 数组的 C 语言代码：

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
void GetNext(char* arr2, int* next)//arr2为字串
{
	int i = 0;
	int k = -1;
	int len2 = strlen(arr2);
	next[0] = -1;
	while (i < len2)
	{
		if (k == -1 || arr2[i] == arr2[k])//k==-1时有两种情况：第一种是一开始k就为-1，第二种是k=-1是不能再回溯。
		{
			k++;//若相等则k一定只加1
			i++;//子串往后移一位里放next的值
			next[i] = k;//放入next的值
		}
		else
		{
			k = next[k];//字符不同则回溯
		}
	}
}
int KMP(char* arr1, char* arr2) //arr1为主串，arr2为字串
{
	assert(arr1 && arr2); //保证传入的指针不是空指针
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	if (len2<0 || len2>len1)
	{
		return -1;
	}
	if (len1 == 0 || len2 == 0)   //两种不可能的情况
	{
		return -1;
	}
	int* next = (int*)malloc(sizeof(int) * len2);//为next数组动态开辟空间
	GetNext(arr2, next);
	int i = 0;
	int j = 0;
	while (j == -1 || i < len1 && j < len2)
	{
		if (arr1[i] == arr2[j])//比较相等均后移一位
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];//不相等则回溯子串，主串不动
		}
	}
	if (j >= len2)
	{
		return i - j;//返回主串与字串开始匹配到成功的开始位置
	}
	return -1;//子串与主串没有可匹配的字符串
}
int main()
{
	char arr1[] = "abababcabc";                    
	char arr2[] = "abcabc";
	printf("%d", KMP(arr1, arr2));
	return 0;
}

四、KMP算法的具体实现

假设主串 A 为 “ababcabcacbab”，模式串 B 为 “abcac”，则 KMP 算法执行过程为：

• 第一次匹配如图八所示，匹配结果失败，指针 j 移动至 next[j] 的位置：
  图八：
  
• 第二次匹配如图九所示，匹配结果失败，依旧执行 j=next[j] 操作：
  图九：
  
• 第三次匹配成功，如图十所示：
  图十：
  
  很明显，使用 KMP 算法只需匹配 3 次，而同样的问题使用 BF 算法则需匹配 6 次才能完成。

五、KMP算法的时间复杂度

现在我们分析一下KMP算法的时间复杂度：
KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)，只为next数组开辟了m个int字节大小的空间。相比于朴素的模式匹配时间复杂度O(m*n)，KMP算法提速是非常大的。

六、next数组的改进–nextval数组及具体代码

图十一：

例如，在图十一中的a），当匹配失败时，Next 函数会由图十一的 b) 开始继续进行模式匹配，但是从图中可以看到，这样做是没有必要的，纯属浪费时间。应该直接从第一个字符‘A’重新开始匹配。那么如何改进next数组呢？

图十二：

使用精简过后的 next 数组在解决例如模式串为 “aaaaaaab” 这类的问题上，会大大提高效率，如图十二所示，精简前为 next1，精简后为 next2。当然如果人为来求，将需要先求出next的数组后才能求得nextval数组。

结论：如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。

next数组改进后的代码：

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
void GetNext(char* arr2, int* next)
{
	int i = 0;
	int k = -1;
	int len2 = strlen(arr2);
	next[0] = -1;
	while (i < len2)
	{
		if (k == -1 || arr2[i] == arr2[k])
		{
			k++;
			i++;
			if (arr2[i] == arr2[k])//进入第一个if语句后向后一位的字符该arr2[i]与arr2[k]仍然相等则直接一次性回溯到位
			{
				next[i] = next[k];
			}
			else     //arr2[i] ！= arr2[k]
			{
				next[i] = k; //不用多次回溯，跟next数组一样
			}
		}
		else
		{
			k = next[k];
		}
	}
}
int KMP(char* arr1, char* arr2)
{
	assert(arr1 && arr2);
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	if (len2<0 || len2>len1)
	{
		return -1;
	}
	if (len1 == 0 || len2 == 0)
	{
		return -1;
	}
	int* next = (int*)malloc(sizeof(int) * len2);
	GetNext(arr2, next);
	int i = 0;
	int j = 0;
	while (j == -1 || i < len1 && j < len2)
	{
		if (arr1[i] == arr2[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= len2)
	{
		return i - j;
	}
	return -1;
}
int main()
{
	char arr1[] = "abababcabc";                      
	char arr2[] = "abcabc";
	printf("%d", KMP(arr1, arr2));
	return 0;
}

七、最后的话

实不相瞒，作者对KMP算法的了解一开始非常懵，只有不断重复思考、复习与亲自敲代码的练习如今才对KMP算法非常了解，才有了这篇博客得以展现给大家。当然如果对KMP算法还有什么误区与此篇博客需要改进的地方可私聊讨论。