KMP算法详解

　

kmp算法

首先感谢大佬博主v_JULY_v（v_JULY_v）在从头到尾彻底理解KMP（2014年8月22日版）一文中给我在写博客组织语言上的启发，以及部分图片的转载。

KMP算法是一种字符串模式匹配算法，不同的来源讲解方式也不一样，很容易混乱，在这里以一种特殊的方式来讲解KMP算法，希望大家不再被这个问题所困扰。

一. 一些基础问题

1. 什么是字符串的模式匹配？

   给定两个串S=“s₁s₂s₃ …s_n”和T=“t₁t₂t₃ …t_n”，在主串S中寻找子串T的过程叫做模式匹配，T称为模式。

2. 如何寻找？

   我们先从比较好理解的暴力匹配（朴素模式匹配BF算法）开始，进而引出KMP算法。

二. 暴力匹配（朴素模式匹配BF）

规定i是主串S的下标，j是模式T的下标。现在假设现在主串S匹配到 i 位置，模式串T匹配到 j 位置。

• 如果当前字符匹配成功（即S[i] = T[j]），则i++，j++，继续匹配下一个字符；
• 如果失配（即S[i] != T[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯到本次失配起始字符的下一个字符，j 回溯到0。

int BF(char S[],char T[])
{
	int i=0,j=0;
	while(S[i]!='\0'&&T[j]!='\0')
	{
		if(S[i]==T[j])
		{
			i++;
			j++;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(T[j]=='\0') return (i-j);     //主串中存在该模式返回下标号 
	else return -1;     //主串中不存在该模式 
}

我们用一个例子来说明一些这个算法：现在有主串S：ababcabcacbab，模式串T：abcac。我们来看一下是如何匹配的。i从0开始，j也从0开始。

在第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i回溯到1，j回溯到0。

第二次匹配中，i从1开始，j从0开始。当i=1，j=0时匹配失败，此时i回溯到2，j回溯到0。

第三次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i回溯到3，j回溯到0。

第四次匹配中，i从3开始，j从0开始。当i=3，j=0时匹配失败，此时i回溯到4，j回溯到0。

第五次匹配中，i从4开始，j从0开始。当i=4，j=0时匹配失败，此时i回溯到5，j回溯到0。

第六次匹配中，i从5开始，j从0开始。i=10，j=5，T中全部字符比较完，匹配成功，返回本次匹配起始位置下标i - j。（i=9和j=4的时候匹配成功，i和j会再加一次，所以i=10，j=5）

可见，如果i已经匹配了一段字符后出现了失配的情况，i会重新往回回溯，j又从0开始比较。这样浪费的大量的时间。在第三次匹配结束后，我们可以发现：i=3和j=0，i=4和j=0以及i=5和j=0是不必进行的，因为从第三次部分匹配过程中我们可以得出，主串中第3，4，5个字符必然是‘b’，‘c’，‘a’（即与模式串的第1，2，3个字符分别对应相等），而模式的首字符是‘a’，它分别与‘b’，‘c’不等，与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较，很明显会加快进程。这样就引出了我们的KMP算法，不回溯i，加快匹配效率。

三. KMP算法

1. 背景

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。

2. 算法流程 （这部分读完可能会有很多问题，没关系，我们会针对每一步进行详细的讲解）

规定i是主串S的下标，j是模式T的下标。现在假设现在主串S匹配到 i 位置，模式串T匹配到 j 位置。

• 如果j = -1，则i++，j++，继续匹配下一个字符；
• 如果S[i] = T[j]，则i++，j++，继续匹配下一个字符；
• 如果j != -1，且S[i] != P[j]，则 i 不变，j = next[j]。此举意味着失配时，接下来模式串T要相对于主串S向右移动j - next [j] 位。

int KMP(int start,char S[],char T[])
{
	int i=start,j=0;
	while(S[i]!='\0'&&T[j]!='\0')
	{
		if(j==-1||S[i]==T[j])
		{
			i++;         //继续对下一个字符比较 
			j++;         //模式串向右滑动 
		}
		else j=next[j];
	}
	if(T[j]=='\0') return (i-j);    //匹配成功返回下标 
	else return -1;                 //匹配失败返回-1 
}

到这里，我们一点点来引出问题，我们来一一解答（后面的问题引出可能还会引出另一个问题，为方便读者阅读，问题标注成蓝色，对应问题解决的地方标注成红色）：

（1）next是什么？？？它是怎么来的？？？

首先我们来解释一个名词：最长公共前后缀。假设有一个串P=“p₀p₁p₂ …p_j-1p_j”。如果存在p₀p₁…p_k-1p_k = p_j-kp_j-k+1…p_j-1p_j，我们就说在P串中有一个最大长度为k+1的公共前后缀。

（2）如何寻找前后缀？？？

• 找前缀时，要找除了最后一个字符的所有子串。
• 找后缀时，要找除了第一个字符的所有子串。

问题（2）已解决

现在有串P=abaabca，各个子串的最大公共前后缀长度如下表所示：

这样，公共前后缀最长长度就会和串P的每个字符产生一种对应关系：

这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。

接下来我们就用这个表来引出next数组，next 数组的值是除当前字符外（注意不包括当前字符）的公共前后缀最长长度，相当于把上表做一个变形，将表中公共前后缀最长长度全部右移一位，第一个值赋为-1。例如c对应next值的意义是，c之前（不包括c）的子串abaab所拥有的公共前后缀最长长度为2，我们称next数组中的值为失效函数值，也就是c的失效函数值为2。（当然这是我们手动推得，我们后续会用编程思想来推得next数组）

我们手动推得了next数组，那就来体验一下KMP算法的流程：现在有主串S：ababcabcacbab，模式串T：abcac。i从0开始，j也从0开始。

根据上述方法可以知道，T的中每个字符对应的失效函数值为：

第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i不动，next[j]=next[2]=0，接下来模式串T要相对于主串S向右移动j - next [j] = 2 位，j回溯到0。

第二次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i不动，next[j]=next[4]=1，接下来模式串T要相对于主串S向右移动j - next [j] = 3位，j回溯到1。

第三次匹配中，i从6开始，j从1开始。当i=10，j=5时匹配成功，返回i - j = 5。

我们根据next数组进行匹配，不失一般性的话，我们做如下总结：

当主串S与模式串P失配时，j=next[j]，P向右移动j - next[j]。也就是当模式串P后缀p_j-kp_j-k+1…p_j-1与主串S的s_i-ks_i-k+1…s_i-1匹配成功，但是p_j和s_i失配时，因为next[j]=k，相当于在不包含p_j的模式串中有最大长度为k的相同前后缀，也就是p₀p₁…p_k-1 = p_j-kp_j-k+1…p_j-1，所以令j = next[j]，让模式串右移j - next[j]位，使模式串p₀p₁…p_k-1 与主串s_i-ks_i-k+1…s_i-1对齐，让p_k和s_i继续匹配。如下图所示：

KMP的next数组告诉我们：当模式串中的某个字符跟主串中的某个字符失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟主串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

问题（1）已解决

好了，至此我们把next原理全部讲完，但是我们不能只停留在手动推导的层面上，我们再从编程下手继续理解next数组，最后再推出KMP算法。

3. 递推求next数组

我们很容易的可以知道，next[0] = -1。next[1] = 0也是容易推得的。那么（3）当j>1时，如果我们已知了next[j]，那么next[j+1]怎么求得呢？？？

假定我们给定了某模式串，且已知next[j] = k，现在求得next[j+1]等于多少。

我们分两种情况分析：

1. 当p_k=p_j时，next[j + 1] = next[j] + 1 = k + 1，代表字符E前的模式串中，有长度k+1 的最大公共前后缀。

   

2. 当p_k ! = p_j时，说明p₀p₁…p_k-1p_k != p_j-kp_j-k+1…p_j-1p_j，这时ABC与ABD不相同，也就是字符E前的模式串中没有长度为k+1的最大公共前后缀，所以next[j + 1] = next[j] + 1不再适用，我们只能寻找更短的最大公共前后缀。

   

   这样看来，如果我们能在p₀p₁…p_k-1p_k中不断递归索引k = next[k]，找到一个字符p_k’，也是D的话，那么最大公共前后缀长度就为k’+1。此时p_k’=p_j，且p₀p₁…p_k’-1p_k’ = p_j-k’p_j-k’+1…p_j-1p_j。从而next[j+1] = k’ + 1 = next[k’] + 1。否则前缀没有D，next[j+1] = 0。

问题（3）已解决

（4）为什么递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？？？我们用这张图来分析：

在p_k != p_j时，k = next[k]，用p_next[k]去跟p_j继续匹配。为什么不用其他值和p_j匹配呢？我们可以看到，在p_j之前，有一段长度为k的已匹配串；在p_k之前有一段蓝色的已匹配串，说明p_k字符前有一段长度为next[k]的最大公共前后缀（蓝色的那段）。如果p_k != p_j，说明p₀p₁…p_k-1p_k != p_j-kp_j-k+1…p_j-1p_j，那么我们只能找更短的最大公共前后缀，此时因为p_k和p_next[k]前面的蓝色串已完全匹配，如果p_next[k]能和p_j匹配 ，那么我们便找到了我们需要的串。如果还是不匹配，下一步p_{next[next[k]…]}去跟p_j继续匹配,直到找到长度更短公共前后缀。

问题（4）已解决

综上，我们可以写出求next数组的递推代码：

void GetNext(char T[])
{
	int j=0,k=-1;
	next[j]=k;
	while(T[j]!='\0')
	{
		if(k==-1||T[j]==T[k])
		{
			j++;
			k++;
			next[j]=k;
		}
		else k=next[k];
	}
}

其实，我们在分析的过程中可以发现，k=next[next[k]…]这一步其实非常的类似于递归。因此我们也给出递归的代码供读者参考。

int GetNext(int j,char T[])
{
	if(j==0)return -1;
	if(j>0)
	{
		int k=GetNext(j-1,T);
		while(k>=0)
		{
			if(T[j-1]==T[k])return k+1;
			else k=GetNext(k,T);
		}
		return 0;
	}
	return 0;
}

文章最后发布于: 2019-04-25 22:05:03

相关阅读

Dlib库landmark算法解析（ERT 集成回归树）

landmark是一种人脸部特征点提取的技术，Dlib库中为人脸68点标记，在《调用Dlib库进行人脸关键点标记》一文中有效果和标定点序号的示

MySQL information_schema 详解

大家在安装或使用MYSQL时，会发现除了自己安装的数据库以外，还有一个information_schema数据库。information_schema数据库是做什么

定时任务ScheduledThreadPoolExecutor的使用详解

定时任务ScheduledThreadPoolExecutor的使用详解 前短时间需要用到一个定时器处理蓝牙设备接收的数据，并且需要处

基于Pairwise排序学习的因子分解推荐算法

摘要： 针对基于内存的协同过滤推荐算法存在推荐列表排序效果不佳的问题，提出基于Pairwise排序学习的因子分解推荐算法（简称Pairwise-

Socket通信详解

网络上的两个程序通过一个双向的通信连接实现数据的交换，这个连接的一端称为一个socket。socket本质是编程接口(API)，对TCP/IP的封