字符串匹配问题（BF，KMP）

• BF算法
• • 代码实现
• KMP算法
• • 核心创建next数组
  • 完整代码

BF的全称为Brute Force，所以BF算法又叫做暴力算法。下面我们来看看BF算法解决字符串匹配问题的一个例子，相信看完之后，BF算法解决此问题中的难点你就明白了。

其实BF算法解决字符串匹配问题是很简单的，比较让人难以理解的就是他的返回值i-j+1和为什么最后打印i-j，在图中已经将此问题说的很清楚了。

#include
#include
#include
using namespace std;


int BF(char* str, char *sub)   //str表示主串，sub表示子串
{
	assert(str != NULL&&sub != NULL);
    
	int lenstr = strlen(str);
	int lensub = strlen(sub);

	int i = 0, j = 0;
	while (i < lenstr&&j < lensub)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;  //表示匹配不成功后i要返回的位置，不懂的可以看下面的图
			j = 0;  //j则返回到起始位置
		}
	}
	if (j >= lensub)   //此时说明匹配成功
	{
		return i - j; //返回匹配成功的起始下标
	}
	return -1; //没有匹配成功
}

int main()
{
	printf("%dn", BF("ababababcd", "abcd"));  //6
	printf("%dn", BF("ababababcd", "abcdf")); //-1
	printf("%dn", BF("ababababcd", "ab"));//0
	return 0;
}

时间复杂度：O(M*N) M和N分别为主串和子串的长度。

我们发现如果数据量一大，那么这个算法十分的低效，那有没有更加高效的算法了？当然是有的，下面我们来看看KMP算法。

这儿我们主要讲解KMP算法最核心也是最主要的部分，next数组的如何形成。 至于KMP算法的基础部分B站或者博客上有许多对它的讲解，这儿博主就不在讲解了，不懂的小伙伴可以去网上自己学习下。

void Creatnext(char* sub, int *next, int lensub)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int k = 0;
	while (i < lensub)
	{
		if (k == -1 || sub[i - 1] == sub[k])
		{
			next[i] = k+1;	
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

注意：
1.这里我们是从头开始求的，并不知道next[2]等于什么，所以我们要利用此时的条件，我们知道了next[1]为多少，也就是i的前一个next是多少，所以只要有sub[i-1]=sub[k],我们就可以退出next[i]=k+1。这个很抽象，最好要结合画图去理解。
2.记录完一个位置的next之后，就要i++去记录下一个位置的next，k也要++，因为这个时候你回退的位置也发生了变化，而且有个规律，k每次增加最多只能增加1,但是减少就不一定了。
3.k==-1要处理下，这时说明回退到-1这个位置都没有找到一样的，之后仍然要进行if括号里面的代码。
4.k=next[k]，表示回退时的位置与sub[i-1]不一样就一直回退，直到回退到k==-1。

剩余的代码部分其实和BF算法差不多。下面来看看完整的代码。

#include
#include
#include
#include
using namespace std;

void Creatnext(char* sub, int *next, int lensub)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int k = 0;
	while (i < lensub)
	{
		if (k == -1 || sub[i - 1] == sub[k])
		{
			next[i] = k+1;	
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

int KMP(char* str, char* sub)
{
	assert(str != NULL&&sub != NULL);
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	

	int* next = (int *)malloc(sizeof(int)*lensub);
	if (next == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}

	Creatnext(sub, next, lensub);

	int i = 0;
	int j = 0;
	while (i= lensub)
	{
		return i - j;
	}
	return -1;
}
int main()
{
	printf("%dn", KMP("ababababcd", "abcd"));  //6
	printf("%dn", KMP("ababababcd", "abcdf")); //-1
	printf("%dn", KMP("ababababcd", "ab"));//0
	return 0;
}

这篇文章知识博主目前对KMP算法的浅薄认识，相信随着日后的学习，一定会对它有更深刻的理解。日后如果有什么所想，也会添加到此文章中。