BF算法优化-------KMP算法_bf算法的时间复杂度改进

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

 上图中我们眼睛可以看出来k的位置  但是在程序中实现呢 ？

通常就是弄个next数组来存放应该j应该回退的位置k  这个数组怎么求才是这个KMP算法的核心所在！

 数学推导过程看这个就好  他讲的就是next[1] = 0  子串开头下标从1开始的：

一定要看这个  讲的超级好！！！！！！！！！！！！！！！！！！！！！！
KMP算法之求next数组代码讲解_哔哩哔哩_bilibili本视频旨在解决KMP算法中如何用代码求解next数组的问题，并对其中的实现代码进行了逐行推演解释，由于up主知识水平有限，如果其中有不足的地方希望大家多多谅解~O(∩_∩)O~~https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=7521948390163041197&spm_id_from=333.337.0.0

next数组所求代码：

int *Get_next(const char *sub)
{
	//assert
	int len_sub = strlen(sub);
	int *next = (int*)malloc(sizeof(int) * len_sub);
	assert(next != 0);
 
	next[0] = -1;
	next[1] = 0;
 
	int j = 1;
	int k = 0;
 
	//通过已知推位置  j是已知  则j+1是未知     
	while(j+1 < len_sub)//未知位置需要合法  所以做了一个判断
	{
		if(sub[j] == sub[k] || (k==-1))//要么相等k++赋值，要么不相等k一直回退，触发了保底机制（k==-1）
		{
			//next[++j] = ++k;
			k++;
			j++;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
 
	return next;
}

KMP_search的代码：

int KMP_Search(const char *str, const char *sub, int pos)//pos代表主串开始查找的下标位置
{
	assert(str!=NULL && sub!=NULL);
	if(pos<0 || pos>=(int)strlen(str))
	{
		//return -1;
		pos = 0;
	}
 
	int len_str = strlen(str);//主串的长度信息
	int len_sub = strlen(sub);//子串的长度信息
	int i = pos;//主串开始位置
	int j = 0;//子串开始位置
 
	
	int *next = Get_next(sub);
 
	while(i<len_str && j<len_sub)
	{
		if((j==-1) || str[i] == sub[j])//如果相等，两者同时向后走，i++,j++
		{
			i++;
			j++;
		}
		else
		{
			//i不回退
			j = next[j];//next[j] == k
		}
	}
 
	//此时while循环退出   两种情况，要么i走出范围   要么j走出范围
	if(j >= len_sub)//如果子串的j走出范围，找到了，返回i-j
	{
		return i-j;
	}
	else//否则没有找到，匹配失败，返回-1
	{
		return -1;
	}
}

KMP算法最难理解的就是next数组的数学推导  剩下的和BF算法基本一毛一样！

“钱可以解决你百分之九十九的不开心，啊？你问还有百分之一的不开心呢 那是不够有钱！”