KMP算法详解，涵盖你对kmp算法所有的不解之处_kmp算法详解及优缺点

1.KMP算法引入

在实现该代码之前，我们要先知道KMP算法是什么，有什么用，和一般的暴力搜索方法比较起来有何种优势。
首先KMP算法是什么：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）
看完上面的概述之后，不难发现KMP算法是用于查找一个字符串里面是否存在我们想要的子串，例如在abcdefg中查找有无abc这个子串
那么他和一般的暴力搜索的优势在哪？举个例子

char arr1[] = "aabaabaac";
char arr2[] = "aabaac";
1
2

暴力搜索：一开始一 一匹配，当匹配到arr2的c时，和arr1的c并不匹配，p1指针重置成arr1数组的第二个元素，p2置回arr2数组的起始位置，由此类推，直到p1走到arr1的末尾或者p2走到arr2的末尾。我们可以发现，这样方法并没有好好利用我们先前匹配成功的部分，每一次查找之前没有任何关系，以至于做了很多的无用功。
那么KMP算法便解决了问题，他最大的优势就在于充分的利用了已匹配的部分，减少了无用匹配次数。

2.KMP算法实现要求

（设被查找的字符串为文本串arr1，想要的字符串的称为模式串arr2）
KMP算法最大的核心就是通过前缀表next记录模式串中首元素到每个元素的子串的最长相等前后缀。什么意思呢？举个例子
首元素到每个元素的子串，即：

char arr[] = "aabaac";//a aa aab aaba aabaa aabaac
1

前缀：包括首字符但不包括尾字符的子串。

char arr[] = "aabaac";//前缀：a aa aab aaba aabaa
1

后缀：包括尾字符但不包括首字符的子串。

char arr[] = "aabaac";//前缀： a ab aba abaa abaac
1

所以例子中的next数组就为

至于数组元素的内容从何而来接下来我将一一介绍：

char arr[] = "aabaac";//a aa aab aaba aabaa aabaac
1

next[0]=0,即a，由于只有一个元素，所以前后缀均是a，所以最长相等前后缀为0
next[1]=1,即aa，前缀a，后缀a，所以最长相等前后缀为1
next[2]=0,即aab，无相等前后缀，所以为0
next[3]=1,即aaba
易错点来了!!!
next[4]=2,即aabaa，可能有同学会问这里不应该是三吗，前缀aab，后缀也aab啊，这里需要强调一点，前后缀不是回文子串，前后缀都应该从一个方向读：也就是aab是不等于baa的，如果子串是aabaab，这时最长相同前后缀便是3。
next[5]=0,即aabaac
介绍完前缀表后，我们应该怎么使用呢？
具体用法：

char arr1[] = "aabaabaac";
char arr2[] = "aabaac";
1
2

当我们p2指到c时，发现文本串和模式串并不相同，这是不再是把p2（见下图）指针置回开头，而是找到next数组中c前一个（即next[p2-1]）的相同前后缀的长度max_lenth，然后从arr2[max_lenth]继续和arr1那个位置匹配。例如：
【找到next数组中c的前一个（即next[4]）的相同前后缀的长度2，然后从arr2[2]继续和arr1那个位置匹配，因为是前一个所以这里需要小心数组越界问题，这里源代码注释会说】


为什么可以这么做呢？很明显利用的前后缀相同的前提。 因为后缀和前缀相同，所以我们节省了匹配前缀的那一段，不就减少了多余操作了吗。
知道了这些，接下来最重要的就是处理next数组的每元素，那怎么样对next数组的元素进行赋值呢？ 对于这样一个模式串

char arr[] = "aabaac";//没错还是我
1

想要求出每一段子串的最长的相同前后缀，我们需要用到两个指标分别指向前缀的尾元素和后缀的尾元素。如图：

如果两个指针指向的元素相同，令pprefix++，然后next[psuffix]=pprefix,随后再psuffix++，如果不相同，令pprefix = next[pprefix - 1]后再比较两个指针指向的元素是否相同，若仍不相同则重复上面操作，直到pprefix=0或者两元素相同时停止，令pprefix++，然后next[psuffix]=pprefix,随后再psuffix++，直到psuffix到达模式串末尾，若以pprefix=0，依然要执行next[psuffix]=pprefix。
看完这里大家有疑问，接下来我为大家统一解释一下
Q1：为什么next[psuffix]=pprefix？我们知道next是用于存储模式串首元素到每个元素的那个子串最长的相同前后缀的长度，而这个长度就是前缀长或者后缀长。
Q2:pprefix = next[pprefix - 1]这一步什么意思？其实求最长相等前后缀也可以等同于子串匹配，只不过这个是在同一个字符串上匹配的，举个例子

char arr[] = "aabaac";//没错又又又是这个模式串
1

这样next数组的赋值操作就完成啦！

3.源代码

{
	int sz1 = strlen(arr1);
	int sz2 = strlen(arr2);
	int* next = (int*)calloc(sz2, sizeof(int));
        int pprefix = 0;//pprefix不仅代表前缀长，也可代表最长相等前后缀
        //next数组元素赋值
	for (int psuffix = 1; psuffix < sz2; psuffix++)//next[0]默认为0  
	{
		//不相等的情况
		while (pprefix>0&&arr2[pprefix]!=arr2[psuffix])
		{
			pprefix = next[pprefix - 1];
		}
		//相等的情况
		if (arr2[pprefix] == arr2[psuffix])
		{
			pprefix++;
		}
		next[psuffix] = pprefix;//更新next
		//printf("%d ", next[psuffix]);//可用于测试你next数组是否正确
	}
	int pmatch = 0;//模式串指针
	int parr1 = 0;//文本串指针
	while (parr1 < sz1&&pmatch<sz2)
	{
		if (arr1[parr1] == arr2[pmatch])
		{
			parr1++;
			pmatch++;
		}
		else
		{
		//首先能走到下面这个if判断条件，说明一定不相等
                //所以如果模式串回到首元素位置，说明文本串指针需要++了
                //同时也避免了数组越界情况
                        if (pmatch == 0)
			{
				parr1++;
			}
			else
			pmatch = next[pmatch - 1];
		}
	}
	free(next);
	next = NULL;
	if (pmatch == sz2)//模式串结束了说明匹配成功
		return 1;
	else
		return 0;
}

作者：璃月偶像刻晴
链接：https://juejin.cn/post/7082384910320664583/
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

若有错误，感谢指出！！！