【字符串匹配算法】BF与KMP算法

一、BF算法

1.1 概念

BF算法，即暴力（Brute Force）算法，是普通的模式匹配算法，BF算法的思想就是将目标串S与字串T的第一个字符进行匹配，若相等，则继续比较S的第二个字串和T的第二个字符；如不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法的时间复杂度位为O(n*m)。

1.2 实现

int BF(const char* str, const char* sub)
{
	//检查
	assert(str && sub);
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	assert(lenstr && lensub);

	int i = 0;
	int j = 0;
	while( i < lenstr&&j<lensub)
	{
		//相等就比较下一个
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		//不相等就将i变到比较的下一个，j归零
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	
	//判断子串是否结束
	if (j == lensub)
		return i - j;
	else
		return -1;
}

二、KMP算法

2.1 概念

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth,J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP的时间复杂度位O(m+n)。
区别：KMP和BF唯一不一样的地方在于KMP主串的i并不会回退，并且j也不会移动到0号位置

2.2 理解

在这里插入图片描述
首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
在这里插入图片描述
接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。
当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。
在这里插入图片描述
因为空格与Ｃ不匹配，搜索词还要继续往后移。

在这里插入图片描述
逐位比较，直到发现C与D不匹配。于是，继续将搜索词向后移动。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

2.3 next()数组

接下来我们来看这么一个子串，推导出它的next()数组：
在这里插入图片描述

KMP算法精髓就在于next()数组：也就是next[j] = k; 来表示，不同的j对应一个k值，这个k就是你将来要移动的j要移动的位置。

K值的规则

规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标0字符开始，另一个j-1下标字符结尾。
不管什么数据next[0] = -1;next[1] = 0;。

2.4 实现

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

int KMP(const char* str, const char* sub, int pos)
{
	//检查
	assert(str && sub);
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	assert(lenstr && lensub);
	
	char* next = (char*)malloc(sizeof(char) * lensub);
	getnext(next, sub);

	int i = 0, j = 0;
	while (i < lenstr && j < lensub)
	{
		if (j==-1||str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}

	free(next);
	if (j == lensub)
		return i - j;
	else
		return -1;
}