KMP模式匹配算法详解

0x01.关于KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

0x02.算法由来

问题：

如果对于一个主串S和一个子串T，要求计算子串T在S中的位置，不存在就返回-1。

问题分析：

对于这个问题，要求计算子串在主串中的位置，那么，按照常规思路，只需要一位一位的去匹配就行了。

普通解法：

//pos为匹配的起点，即从T的第pos位开始匹配
//两个字符串的有效位置都从0开始
int Index(char* S, char* T, int pos)
{
	int i = pos;//控制主串的下标
	int j = 0;//控制子串的下标
	while (i < strlen(S) && j < strlen(T))//保证下标都在有效范围内
	{
		if (S[i] == T[j])//一个字母相等，继续匹配下一个字母
		{
			i++;
			j++;
		}
		else//遇到不匹配的i和j都要回溯
		{
			i = i - j + 1;//上次匹配的首位的下一位
			j = 0;//下次又要从首位开始匹配
		}
	}
	if (j >= strlen(T))//如果j的位置超出有效范围，说明之前的都匹配，那么已经完成了匹配的过程
	{
		return i - strlen(T);//上次匹配的首位
	}
	else
	{
		return -1;
	}
}

问题再度分析：

这个解法通过不断的对i和j进行回溯，保证了一位一位的匹配，肯定是可行的，但我们发现，每次i都要退回匹配的的首位，j每次要退回子串的首位，这样花费的时间代价有点大，我们举一个例子：

假设主串是：acdcdabccaddadc

子串是：acdaac

按照这个算法进行匹配运算，首先，前三位都是匹配的。

第四位开始不匹配，那么按照这个算法，i 和 j 都要分别退回首位。但其实我们会发现没有必要，为什么呢，因为已经匹配的部分字符串中，首位等于末尾，对于 i 来说，前面三位都已经匹配了，回溯到c的位置的时候，由于a和c不等，c位置时一定是不匹配的，对于 j 来说，因为已经匹配的字符串首位等于末尾，所以只要从第二位c开始匹配就行了。

这个时候 i 加1，j回溯到1，继续开始匹配，这个过程，节省了许多的时间。

再来看一个例子：

主串是：acdacdabccaddadc

子串是：acdacdc

首先前6位都是相等的。

从第7位开始不匹配。按照刚才的思路，我们要怎样去匹配才能节省时间呢？

上一次我们观察到已经匹配部分字符串的首位和尾位相等，所以只需要从首位的下一位开始匹配就行了。在这个已经匹配的字符串部分字符串中，首三位acd等于尾三位acd，同样，我们只需要从主串的第7位，子串的第4位开始匹配就行了。

我们再来看一个例子。

主串是：acbdccabccaddadc

子串是：acbdcdc

前面五位已经匹配，从第六位开始不匹配。

此时，我们要怎样才能节省时间呢，是不是主串的 i 还可以接着那个位置开始，j还可以回溯到非首位呢？？我们发现此时不能将j回溯到一个非首位了，那么到底是为什么呢，我们比较一下这三个例子，我们发现不同的地方在于，前面两个例子的已经匹配的部分字符串中，前几位和末几位都有相同的部分，所以我们再次比较的时候，相同的部分就不需要再比较，只需要从不相同的部分开始比较就行了，而第三个例子没有这种有效信息，所以我们不能够这样回溯，既然有的包含一些有效信息，有些没有包含，我们可不可以用一个数组统一记录下这个有效信息呢？

0x03.next数组推导

我们观察上面的例子，发现这个有效的信息是在已经匹配的部分字符串里面，但其实这个部分字符串一定都在子串里面，所以我们只需要对子串的每一个字符都分析它前面字符的有效性，这样，每次匹配的相应的字符的时候，就能够知道它前面字符串的有效性了，一旦遇到不匹配的字符，我们就可以拿出这个有效信息，确定 j 的回溯位置了，那么我们如何表示出这个有效信息呢？我们需要引入两个概念：

前缀：指的是字符串的子串中从原串最前面开始的子串

后缀：指的是字符串的子串中在原串结尾处结尾的子串

理解前缀与后缀：

比如一个字符串是 abcdcd，那么它的前缀有：a,ab,abc,abcd,abcdc,abcdcd。我们发现就是字符串的前几位。

再比如这个字符串 abccdfe，那么它的后缀有：e,fe,dfe,cdfe,ccdfe,bccdfe,abccdfe。我们发现就是字符串的后几位。

那么我们要表示出这个有效信息，就只需要确定每一个部分字符串的最长的相同前缀后缀的长度！！！！

next详细原理

我们现在要做的事是要求出字串中每一个字符的前面字符串的最长的相同前缀后缀的长度，然后用一个数组存储起来，一般这个数组常用next来命名，意思就是在匹配的时候，j要回溯的下一个位置。

那么如何求这个最长的相同前缀后缀的长度呢？

我们来看一个例子：

字符串：abacab

它的的第一个字符，只有一个字符，肯定谈不上前缀后缀相等，就算强加上前缀后缀一个相等，也没有任何用，没有，我们记为0，表示如果匹配不成功，那么 j 需要回溯到0，也就是字符串的首位。

它的第二个字符的前面字符串（包含第二个字符），首位也不相等，那么如果要回溯的话，肯定也是0。

它的第三个字符的前面字符串（包含第三个字符），首位和尾位相等，如果吧匹配不成功，j 要回溯的话，只需要从首位的下一个字符，也就是字符b开始，j要回溯到1。

它的第四个字符的前面字符串（包含第四个字符），首位都不相等，回溯肯定为0。

它的第五个字符的前面字符串（包含第五个字符），首位和尾位相等，回溯为1。

它的第六个字符的前面字符串（包含第六个字符），前两位，和后两位相等，回溯为2，也就是下次从第三个字符开始匹配。

这个字符串的next数组的值应该是[0,0,1,0,1,2]。

假设我们的 j 到某个字符不匹配了，那么 j 肯定就是等于它前面字符串（不包含自己，因为前面的字符串已经匹配），j=next[j-1]；

上面我们提到了KMP算法的大概思想，就是遇到不匹配的时候，去找它上一个字符的next值，让j合适的回溯，而i不变。

那么对于子串的next推导，其实也可以看成是自己对自己的匹配，因为next[0]肯定是0，然后之后的继续匹配（求最长的相同前缀后缀长度），就可以利用之前已经求出的next数组中的值，对 j 进行合理的回溯。

我们先来看一下具体求next数组的代码：

//求解next数组
void Cal_Next(char* T,int *next)
{
	int k = -1;//k控制匹配过程中的下标变换
	next[0] = k;//next[0]必定为-1
	//i控制求解过程中的下标变化，每一次大循环，一定会得到一个next值
	//i此时等于多少，就是在求next数组中该下标所对应的值
	for (int i = 1; i < strlen(T); i++)
	{
		//如果k=0，那么说明k要从第一个字符开始匹配，直接跳到下面判断第一个字符是否等于当前要匹配的字符
		//此时的k是上一次匹配完后k的位置，如果k处的值不等于此时i处的值，那么k要不断的回溯，直到找到合适的能接上的值
		while (k > -1 && T[k+1] != T[i])
		{
			k = next[k];
		}
		if (T[k+1] == T[i])//判断以下是否可以接上，可以就k+1
		{
			k++;
		}
		next[i] = k;//得到next值
	}
}

在这个算法里面，k的值从-1开始，每次比较也都是比较k+1位，next数组的值是真实的最长值-1。目的是保证k永远比next[k]要小，避免死循环。

为了更好的理解这个算法，我们来一步一步的模仿以下计算机的运行。

还是原来的字符串：abacab。

第一步，next[0]=-1，这个没有话说，第一个字符，肯定是-1。

第二步，进入for循环，此时k=-1，跳过第一个小循换，直接判断T[0]和T[1]的值，此时不相等，那么next[1]=-1。

第三步，i=2，k=-1，直接判断T[0]和T[2]的值，此时相等，那么k++，next[2]=0。

第四步，i=3，k=0，判断T[1]和T[3]的值是否相等，其实真实意义就是，i 往后加一个值，看这时，还能不能接上上次前缀后缀相等的部分，如果可以接上，那么长度肯定加1了，如果不可以，回溯继续判断。此时T[1]和T[3]不相等，那么进入小循环，开始回溯，这个回溯的值就是上次k位置的next值，k=next[k]=next[1]=-1，此时跳出循环，判断T[0]和T[3]是否相等，也不相等，那么，next[3]=-1。

第五步，i=4，k=-1，判断T[0]与T[4]是否相等，相等，k++，next[4]=0。

第六部步，i=5，k=0，判断T[1]与T[5]是否相等，相等，k++，next[5]=1。

到此，程序结束，我们发现计算结果和我们之前的完全一致，通过不断的循环演示这个运行过程，我们可以发现，它的原理就是利用已经产生的next数组的值，去往后面接，能接上，就加一，不能接上就回溯，如果回溯到了0，那么直接判断首位和末尾的值的情况。我们发现这个过程其实就是这个字符串不断的对自身进行匹配，最后得到了完整的next数组的值。

0x04.KMP算法代码

有了上述基础，我们就能容易的得出KMP算法的代码了。

返回第一个找到的下标：

int Index_KMP(char* S, char* T, int pos)
{
	int next[MAXSIZE];
	Cal_Next(T, next);
	int i = pos;//i控制主串下标
	int j = 0;//j控制子串下标
	while (i < strlen(S) && j < strlen(T))
	{
		if (j==0||S[i] == T[j])//如果子串回溯到0了，同样往后比较一位
		{
			i++;
			j++;
		}
		else
		{
			j = next[j-1]+1;//注意是前一位的next值加1
		}
	}
	if (j >= strlen(T))
	{
		return i-strlen(T);
	}
	else
	{
		return -1;
	}
}

每找到一个输出一个:

void Index_KMP(char* S, char* T, int pos)
{
	int next[MAXSIZE];
	Cal_Next(T, next);
	int i = pos;//i控制主串下标
	int j = 0;//j控制子串下标
	while (i < strlen(S) && j < strlen(T))
	{
		if (j==0||S[i] == T[j])//如果子串回溯到0了，同样往后比较一位
		{
			i++;
			j++;
		}
		else
		{
			j = next[j-1]+1;//注意是前一位的next值加1
		}
		if (j >= strlen(T))
		{
			printf("在第 %d 个位置匹配到字符串\n", i - strlen(T)+1);
			j = 0;
		}
	}
}

0x05.KMP算法改进

 问题：

KMP算法虽然已经比较完善，但存在一个这样的问题：

比如：

主串是：cccccaabccaddadc

子串是：cccccdc

那么刚开是匹配的时候，前5位相等。

从第6位开始不匹配，此时的next数组中的值是[-1,0,1,2,3,-1,0]。此时j应该回溯到next[4]+1=4，j=4，如下图：

很明显，下一位也是不匹配的，那么j回溯到next[3]+1=3，如下图：

下一位又不匹配，然后j又要回溯到next[2]+1=2，如下图：

 又不匹配，又回溯到next[1]+1=1，如下图：

 不匹配，j回溯到next[0]+1=0，也就是j回溯到了首位。

从这些回溯我们可以看出，其实中间的回溯都是没有意义的，因为前面几个字符都与当前要回溯的那个字符相同，再怎么回溯，也是不等于，这些不断回溯的步骤，就造成了时间的浪费，于是，我们得想办法进行改进，这个改进毫无疑问是要再next数组中进行的，因为后面的字符等于前面的字符，那么回溯回去，没有任何意义，还是要继续回溯，所以我们要针对这个字符相等下功夫，如果再在这个字符串匹配到第一个字符不相等的时候，它的回溯的值就等于首字符的next值得化，那么中间这些过程是没必要的。

所以我们只需要在next数组中，将子串中重复相等的部分，用相同的值定义即可。

改进后的求next数组代码见下文Cal_Next3。

0x06.其他下标意义下的KMP算法

字符串起点：从1开始，0号下标一般存储字符串的大小

next数组起点：下标从1开始，0号下标不考虑

next数组下标含义：前一个字符的真实的相同前缀后缀大小加一

next数组的值的含义：前一个字符的真实长度+1

//下标从1开始
void Cal_Next2(char* T, int* next)
{
	int i, j;
	i = 1; 
	j = 0;
	next[1] = 0;//第一个肯定为0 
	while (i < strlen(T))
	{
		if (j == 0 || T[i] == T[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];//回溯
		}
	}
}

//下标从1开始
void Cal_Next3(char* T, int* next)
{
	int i, j;
	i = 1;
	j = 0;
	next[1] = 0;//第一个肯定为0 
	while (i < strlen(T))
	{
		if (j == 0 || T[i] == T[j])
		{
			i++;
			j++;
			if (T[i] != T[j])//当前字符与前缀字符不相同
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];//与前缀字符相同，取前缀字符的值
			}
		}
		else
		{
			j = next[j];//回溯
		}
	}
}

//下标从1开始
int Index_KMP1(char* S, char* T, int pos)
{
	int next[MAXSIZE];
	Cal_Next3(T, next);
	int i = pos;//i控制主串下标
	int j = 0;//j控制子串下标
	while (i <= strlen(S) && j <= strlen(T))
	{
		if (j == 0 || S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > strlen(T))
	{
		return i - strlen(T);
	}
	else
	{
		return -1;
	}
}

0x07.总结

要理解KMP算法必须知道next数组的下标，及下标对应值的含义，不同的地方，大家对它值的具体表述不一样，比如有的next数组表示的最长长度不包含自身，有的存储的不是真正的最长长度，而是要加上1，目的是为了区分0下标，还有的字符串从1开始，用0存储长度，因为这些因素，造成了KMP算法理解起来有些吃力，但其实不管怎么变，这个核心思想是一样的。在本文中，对这些细节是这样处理的：

字符串起点：文中所有字符串起点都从0开始

next数组起点：next数组下标从0开始

next数组下标含义：是这个字符之前（包含这个字符）的最长相同前缀后缀的大小

next数组中的值的含义：是真实含义的值-1

KMP算法高度利用了字串自身的性质，通过子串能够得到更多的有效信息，从而节省不必要的比较，在数据量信息比较大时，优势明显，如果信息量不大，优势不是很明显。