用最通俗易懂的语言描述KMP算法及证明

KMP 算法是一种字符串模式匹配算法，它可以实现在 O（n+m）的时间复杂度下完成串的模式匹配。对于刚刚接触KMP 算法的人来说，一般是都很难理解：为什么KMP 算法可以完成模式匹配，KMP 中的 next 数组又究竟是什么?

下面我将简单讲解一下我个人对KMP 算法的的理解，以及数学证明。

KMP 算法的简单理解

首先假设KMP 算法中，用 S 来表示主串，用 i 遍历主串；用 T 来表示待匹配的串，用 j 遍历待匹配串。然后在 KMP 算法匹配过程中 i 是一直递增而无需回溯的。

现在假设有一个主串 S：

一个待匹配的串 T：

要求找到串 T 在主串 S 中第一次出现的地方，下面使用 KMP 算法的核心思想进行模拟匹配：

• （1）从主串 S 和串 T 的开头开始匹配，假设 S0——S4 = T0——T4，此时匹配到了 S5 和 T5 位置，并且 S5≠T5；

• （2）我们希望 S 的索引  i  不回溯，那么我们可以通过移动 T 的索引 j ，使得 T 相对 S 往右移动，使得 j 之前的 T 的子串与 S 匹配，并且希望移动的距离最小；

• （3）假设当 j 移动到 T3 位置时，T3 之前的子串 T0——T2 = S2——S4；

• （4）然后再判断 S5 与 T3 是否匹配，如果匹配，i 和 j 同时递增，继续匹配余下的；如果不匹配，则重复以上步骤；

由上面可以看出，KMP 算法的核心在于步骤（2）（3），串 T 的 j 究竟要回溯多少的距离。下面来分析一下：

从步骤（1）知道 S2 S3 S4 = T2 T3 T4  

从步骤（3）知道 S2 S3 S4 = T0 T1 T2

因此 T0 T1 T2 = T2 T3 T4  

发现了没有，T0 T1 T2 是串 T0 T1 T2 T3 T4 的前缀，T2 T3 T4 则是其后缀，前缀与后缀相等。

也就是说，如果我们能找到前缀和后缀最长交集，也就知道了 j 究竟要回溯到什么位置。

步骤（2）的图

就步骤（2）而言，T5 之前的子串 T0 T1 T2 T3 T4 的

前缀集合为{T0、T0 T1、T0 T1 T2、T0 T1 T2 T3}；

其后缀集合为{T4、T3 T4、T2 T3 T4、T1 T2 T3 T4}；

假设 T0 T1 T2 T3 ≠ T1 T2 T3 T4 且 T0 T1 T2 = T2 T3 T4 

那么子串 T0 T1 T2 T3 T4 前缀和后缀最长交集的长度即为 3。

所以在步骤（3）中，j 应当移动到 T3 位置，使得 j 之前的子串即为上面所求的最大交集 T0 T1 T2。

而 KMP 算法中的 next 数组中的数据正是根据前缀和后缀的最大交集长度所得出，表示的是当 j 位置发生不匹配时的下一个 j 的位置。

比如说，当 j=3 时，发生了不匹配，那么 j 应当移动到 next[3]的位置（也就是令 j=next[3]）。

求 next 数组算法代码实现

下面代码中的数组的第 0 个元素都是用来表示串的长度，而并不表示串的第一个元素。

代码实现并不唯一，next 数组的值也并不唯一，因情况而定。

比如说，如果数组的第 0 个元素不用来表示串的长度，而是表示串的第一个元素，那么 next 数组的值的求法也会有所改变。

//KMP 算法中的 next 数组求法示例代码
void find_next(char T[], int next[])
{
	i=1;
	next[1]=0;//next[1]=0 表示当前已经没有元素与主串中的匹配了
	j=0;
	while(i<=T[0])
	{
		if(j==0 || T[i]==T[j])
		{
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}