KMP算法——我欲修仙（功法篇）

「爱情、让人受尽委屈。」 2024-04-11 13:24 137阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]  
> 学习名言：莫等闲、白了少年头，空悲切。——岳飞

--------------------

## 系列文章目录 ##

第一章 ❤️ [学习前的必知知识][Link 3]  
第二章 ❤️ [二分查找][Link 4]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言???
 *  BF算法
 *  KMP算法
 *   *  介绍:
     *  算法主体
     *  next\[\]数组
 *  总结：

--------------------

## 前言??? ##

进入修仙界你会遇见许多新奇事务，认识新的好友，还有许多奇遇，那么废话少说让我们进入到今天的冒险吧!

![在这里插入图片描述][5aa4da9d0a714976b0cf3df0623a13ec.jpeg_pic_center]

--------------------

## BF算法 ##

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

![在这里插入图片描述][720a8476ee4842219f705d2857c9abd8.gif_pic_center]

int BF( char* b,  char* a)
    {
        
    
    	int i = 0, j = 0; 
    	int ret = i;//ｉ用来控制主串，ｊ用来控制子串，ret用来记录若有完整的匹配的字符串时，该字符串的起始位置
    	//当主串和子串都不为'\0'时，进入循环进行比对
    	while (*(b + i) && *(a + j))
    	{
        
    		//如果对应元素相同，则都指向下一位
    		if (*(b + i) == *(a + j))
    		{
        
    			i++;
    			j++;
    		}
    		//不同，则让i回到主串的上一次比较过的元素的第一个元素的后一元素，j赋为0，子串重新比对，
    		//ret则等于新的起始位置
    		else
    		{
        
    			i = i - j + 1;
    			j = 0;
    			ret = i;
    		}
    	}
    	//若主串对应的元素为０，则代表遍历完成，主串没有与子串相匹配的字符串，
    	if (*b == '\0')
    	{
        
    		return -1;
    	}
    	//if如果不执行，下面这个return便会执行。返回下标。
    	return ret;
    }

显然这种暴力的算法并不高效，于是KMP算法就诞生了。

## KMP算法 ##

### 介绍: ###

> KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

KMP算法主要分为两部分：1.算法主体 2.获取next\[\]数组

### 算法主体 ###

让我们忽略next\[\]的由来，只是关注算法主体，算法可以写成

int KMP_S(char *a,char *b,int Len_p,int Len_s)
    {
        
    	 int i = 0, j = 0;
    	 int* next = build_next(b,Len_s);//获取next[]数组
    	while (i < Len_p)
    	{
        
    		if (*(a + i) == *(b + j))
    		{
        
    			i++;
    			j++;
    		}//如果两个数相同，这两个数组都向下移动   
    		else if (j > 0)
    			j = *(next+j-1);//非第一个字符，从跳过next数重新匹配
    		else
    			i++;//第一个字符匹配时就失配
    		if (j == Len_s)
    		return i - j;//返回下标值
    			
    		
    	}
    }

![请添加图片描述][cee95983b5664242912a5937019df4c2.gif]

### next\[\]数组 ###

next\[\]数值代表的是在匹配失败的时候字串中可以跳过匹配的字符个数，通过观察我们不难发现，我们跳过的字符与后面的字符完全相同，即前缀和后缀相同，所以我们可以认为next\[\]数组的本质就是寻找子串中“相同前后缀的长度，并且一定是最长的前后缀”（不包括其本身）  
我们可以使用递归的方式去求解next\[\]数组：  
![请添加图片描述][0ba92e56642b4b32aa858fd15e2c45bb.gif]

int* build_next(int* b, int Len_s)
    {
        
    	int i, j = 0;
    	int next[MAX] = {
         0 };
    	for (i = 1;i < Len_s;i++)
    	{
        
    		while (j > 0 && *(b + i) != *(b + j))
    		{
        
    			j = next[i - 1];
    
    		}
    		if (*(b + i) == *(b + j))
    		{
        
    
    			next[i] = j;
    		}
    
    	}
    	return next;
    }

## 总结： ##

KMP算法比较难以理解，我发现网上大部分讲解KMP算法的文章都比较难懂事实上在这方面我认为还是通过动画视频的方式可以更加直观的认识到KMP算法的运算方式。  
这里我推荐：[最浅显易懂的 KMP 算法讲解][KMP]

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    #define MAX 100
    int next[MAX] = {
         0 };
    /*int* build_next(int* b, int Len_s)
    {
    	int i, j = 0;
    	int next[MAX] = { 0 };
    	for (i = 1;i < Len_s;i++)
    	{
    		while (j > 0 && *(b + i) != *(b + j))
    		{
    			j = next[i - 1];
    
    		}
    		if (*(b + i) == *(b + j))
    		{
    
    			next[i] = j;
    		}
    
    	}
    	return next;
    }*/
    int* build_next(char* b, int Len_s)
    {
        
    	int next[MAX] = {
         0 };
    	int len = 0, i = 0;
    	while (i < Len_s)
    	{
        
    		if (*(b + len) == *(b + i))
    		{
        
    			len++;
    			next[i] = len;
    			i++;
    		}
    		else if (len == 0)
    		{
        
    			next[i] = 0;
    			i++;
    		}
    		else
    			len = next[len - 1];
    	}
    	return next;
    
    
    }//求解next*/
    int KMP_S(char *a,char *b,int Len_p,int Len_s)
    {
        
    	 int i = 0, j = 0;
    	 int* next = build_next(b,Len_s);
    	while (i < Len_p)
    	{
        
    		if (*(a + i) == *(b + j))
    		{
        
    			i++;
    			j++;
    		}//匹配成功向下移动   
    		else if (j > 0)
    			j = *(next+j-1);//非第一个字符，从跳过next数重新匹配
    		else
    			i++;//第一个字符匹配时就失配
    		
    		if (j == Len_s)
    			for (;j < i;j++)
    			{
        
    				printf("%c", *(a + j));
    				return i - j;
    			}
    		
    	}
    }
    int main()
    {
        
    	char Pst[MAX] = {
         0 };
    	char Sst[MAX] = {
         0 };
    	int Len_p = 0;
    	int Len_s = 0;
    	fgets(Pst, MAX, stdin);
    	getchar();
    	fgets(Sst, MAX, stdin);
    	Len_p = strlen(Pst)-1;
    	Len_s = strlen(Sst);
    	printf("%d %d\n", Len_p, Len_s);
    	KMP_S(Pst, Sst,Len_p,Len_s);
    	return 0;
    }

![在这里插入图片描述][73fbe2eec11a43928c0397deac153b4b.gif_pic_center]  
（部分文字与图片来源于网络，侵权请联系删除）

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129731407?spm=1001.2014.3001.5501
[5aa4da9d0a714976b0cf3df0623a13ec.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/9fc2becf3d6f4e39885ce2f9479bce4f.jpeg
[720a8476ee4842219f705d2857c9abd8.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/19c93685c2b74a0299985851af7a64c9.gif
[cee95983b5664242912a5937019df4c2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/574e699dbde74a7a995ad5521f423dc9.gif
[0ba92e56642b4b32aa858fd15e2c45bb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f93aa3c27782441e999bd10837dd1fa0.gif
[KMP]: https://www.bilibili.com/video/BV1AY4y157yL/
[73fbe2eec11a43928c0397deac153b4b.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/13313b8ffc7e447b8045683d3197e43b.gif