【数据结构与算法】-BF算法与KMP算法原理超详细讲解_bf算法和kmp算法

超详细的BF算法与KMP算法讲解，保姆级解析。一文真正理解KMP算法核心思想，next数组计算原理。

目录

1.字符串匹配问题引入

2.算法

2.1BF(Brute Force)算法

2.2KMP算法

2.2.1KMP算法简介

2.2.2KMP算法核心思想

2.2.3next数组求法

2.2.4next[]数组的求解代码

---

1.字符串匹配问题引入

如图：ABCABCDHIJK为目标串，ABCE为模式串，求模式串在目标串串中的位置？

也就是类似在一篇文章中搜索一个单词，或者一个句子。

先思考一下，你会怎么做?

2.算法

问题：求模式串在目标串串中的位置

目标串：

模式串：

2.1BF(Brute Force)算法

对于上述问题有一个很简单的算法：

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，是一种蛮力算法。

BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

BF算法的步骤：

用i指针指向目标串，用j指针指向模式串

1.i指针取1(A)，j指针取一(A)比较，相等；

2.i指针取2(B)，j指针取二(B)比较，相等；

3.i指针取3(A)，j指针取三(A)比较，相等；

4.i指针取4(B)，j指针取四(E)比较，不相等；

5.i指针回溯，取2(B)，j指针取一(A)比较，不相等；

6.i指针，取3(A)，j指针取一(A)比较，相等；

省略后续步骤。

可以看出来，BF算法思想简单，要实现BF算法非常简单，就不贴代码了。设目标串长m，模式串长n，最坏情况下复杂度为O(m*n)。

慢在了哪里？

关键在于第5步，i指针回溯，回去取序号2，所以增加了复杂度。如果不回去，是不是就快了？

这就引出了KMP算法。

2.2KMP算法

2.2.1KMP算法简介

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

2.2.2KMP算法核心思想

问题：

目标串：

模式串：

还是这个例子，1-3步省略，从第4步开始回顾

4.i指针取4(B)，j指针取四(E)比较，不相等；

5.i指针回溯，取2(B)，j指针取一(A)比较，不相等；

2.1中说到：关键在于第5步，i指针回溯，回去取序号2，所以增加了复杂度。如果不回去，是不是就快了？

注意：不回去不代表下一步是比较4与一！

这样就错了。正确的是：

5.i指针不回溯，继续取4(B)，j指针取二(B)比较，相等；

6.i指针取5(A)，j指针取三(A)比较，相等；

7.i指针取6(E)，j指针取四(E)比较，相等；

8.输出结果:模式串在目标串的位置为3.

问题：

第5步是如何得出？我怎么知道4与二去比较？

再看一下第5步：

5.i指针不回溯，继续取4(B)，j指针取二(B)比较，相等；

因为我们发现3(A)与一(A)相等；也就是3456可能与一二三四相同！

得出KMP算法核心：

用i指针指向目标串，用j指针指向模式串，当发生不匹配，指针i不再回溯，而指针j变换位置！

利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”

所以，整个KMP的重点就在于当某一个字符与主串不匹配时，我们应该知道模式串的j指针要移动到哪？

2.2.3next数组求法

因为在模式串P的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当目标串T[i] != 模式串P[j]时，j指针的下一个位置。

当发现T[i] != P[j]时，模式串P中的1~（j-1）个字符与目标串T中的（i-j+1）~（i-1）肯定是匹配的。

举个例子：i指针取到4，j指针取到四，发现4与四不匹配，那1~3与一~三肯定匹配，这应该很好理解。

转化成公式：P[1 ~ j-1] == T[i-j+1 ~ i-1]​ 

因为i不再回溯，我们想知道目标串T中序号4的字符前面，有几个字符与模式串P前缀相同。

不太好理解，看图

i，j位置的字符不一样，红色标出的肯定一样，我们想知道蓝色的长度，

结果问题就转换成了在模式串P的子串P[1~j-1]中找前缀与后缀一样的最大长度是多少的问题。

问题如果用数学公式来表示是这样的，设长度为k

求P[0 ~ k-1] == P[j-k ~ j-1]​中的k值。

好，接下来就是重点了，怎么求这个（这些）k呢

以下来自博主Liu ZhianKMP算法讲解（next数组求解）_Liu Zhian的博客-CSDN博客_kmp算法next

请看下面的例子：

现在我们知道了next[j]=6，那么怎么求next[j+1]呢？且看下面的分析过程：

既然next[j]=6，这里我们记next[j]=k,在上图中，k对应等于6，也就是说t [ 0 ] . . . t [ k − 1 ] t[0] ... t[k-1]t[0]...t[k−1]和t [ j − k ] . . . t [ j − 1 ] t[j-k] ... t[j-1]t[j−k]...t[j−1]是对应相等的，也就是图上的两个蓝色条。

好，现在我们注意到，t[j]=t[k]，也就是说，如果我们在两个蓝条后面都加一个相等的字符，那肯定也是对应相等的，这种情况最简单了，此时next[j+1]=next[j]+1。

我们再考虑t[j]≠t[k]的情况：

好，既然你两个蓝色条对应相等，那我取其中的一部分，那也肯定是对应相等的，没毛病，我就取下图中绿色这两段：

选取的依据就是next[k]的大小了，我们记next[k]=k’,于是下面的等式成立：
t [ k − n e x t [ k ] ] . . . t [ k − 1 ] = t [ j − n e x t [ k ] ] . . . t [ j − 1 ] t[k-next[k]] ... t[k-1]=t[j-next[k]] ... t[j-1]t[k−next[k]]...t[k−1]=t[j−next[k]]...t[j−1]

又根据next[k]的定义，我们可以得到下面的等式：

t [ 0 ] . . . t [ n e x t [ k ] − 1 ] = t [ k − n e x t [ k ] ] . . . t [ k − 1 ] t[0] ... t[next[k]-1]=t[k-next[k]] ... t[k-1]t[0]...t[next[k]−1]=t[k−next[k]]...t[k−1]

上述两个等量代换，得到

t [ 0 ] . . . t [ n e x t [ k ] − 1 ] = t [ j − n e x t [ k ] ] . . . t [ j − 1 ] t[0] ... t[next[k]-1]=t[j-next[k]] ... t[j-1]t[0]...t[next[k]−1]=t[j−next[k]]...t[j−1]

也就是说，下图中①号对应的黄色条子串和②号对应的绿色条子串是对应相等的：

那么，我们现在只要比较t[j]和t[k’]（注意，这里是k’），也就是图中两个紫色的三角形，如果t[j]=t[k’]，好办，next[j+1]=k’+1;如果t[j]≠t[k’]，额，你还记得我们这种情况下是怎么进来的吗？不就是t[j]≠t[k]嘛！现在又来个t[j]≠t[k’]，而k’=next[k]，自然而然就会想到递归处理了，事实上，它们之间的确满足这个递归。至于递归退出的条件，就是next[0]这个边界值了。

2.2.4next[]数组的求解代码

/*
*	求待匹配串的next数组，递归求解
*/
void get_next_arr_2(char* t, int* next)
{
	next[0] = -1;  // next[0]定义为-1
	next[1] = 0;	 // next[1]肯定是0
	int k;
	for (int j = 2;t[j] != '\0';j++)
	{
		k=next[j-1];
		if (k == -1)
		{
			next[j]=0;
			continue;
		}
		else
		{
			while (t[j-1] != t[k] && k!=-1)
				k=next[k];
			if(t[j-1] == t[k])
				next[j]=k+1;
			else
				next[j] = 0;
		}
	}
}

---