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

优雅的算法 TOMORROW 3个月前 (09-25) 263次浏览 0个评论 扫描二维码

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

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

KMP 算法的简单理解

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

 

现在假设有一个主串 S:

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

一个待匹配的串 T:

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

 

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

  • (1)从主串 S 和串 T 的开头开始匹配,假设 S0——S4 = T0——T4,此时匹配到了 S5 和 T5 位置,并且 S5≠T5;用最通俗易懂的语言描述 KMP 算法及证明

 

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

 

  • (3)假设当 j 移动到 T3 位置时,T3 之前的子串 T0——T2 = S2——S4;用最通俗易懂的语言描述 KMP 算法及证明

 

  • (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  

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

 

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

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

 

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

步骤(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];
	}
}

 

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:用最通俗易懂的语言描述 KMP 算法及证明
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
灵巧的雪糕发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到