字符串匹配算法:BF & KMP

• 1. BF算法
• 2. KMP算法
• • 2.0 引出next数组
• 总结：

1. BF算法

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

假定我们给出字符串 ”ababcabcdabcde”作为主串， 然后给出子串： ”abcd”,现在我们需要查找子串是否在主串中出现，出现返回主串中的第一个匹配的下标，失败返回-1 ;

只要在匹配的过程当中，匹配失败，那么：i回退到刚刚位置的下一个,j回退到0下标重新开始。

/*字符串匹配算法  BF 
str:主串
sub:子串
返回值:返回子串在主串当中的下标。如果不存在返回-1
*/
int BF(const char* str, const char* sub)
{
	assert(str && sub);
	if (str == NULL || sub == NULL)
		return -1;
	int lenStr = strlen(str);
	int lenSub = strlen(sub);

	int i = 0;
	int j = 0;
	while (i < lenStr && j < lenSub)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= lenSub)
		return i - j;
	else
		return -1;
	
}
int main()
{
	printf("%d\n", BF("ababcabcdabcde", "abcd"));//5
	return 0;
}

2. KMP算法

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

1. 首先举例，为什么主串不回退？

2. j的回退位置

2.0 引出next数组

KMP 的精髓就是 next 数组：也就是用 next[j] = k;来表示，不同的 j 来对应一个 K 值， 这个 K 就是你将来要移动的 j要移动的位置。 而 K 的值是这样求的： 1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标 字符结尾。 2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始； 那么next数组的具体是怎么求呢？

练习 1： 举例对于”ababcabcdabcde”， 求其的 next 数组？ -1 0 0 1 2 0 1 2 0 0 1 2 0 0 练习 2： 再对”abcabcabcabcdabcde”,求其的 next 数组？ " -1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0 解释: 练习一：

先将 -1和0填入，当下一步时，j指向a,则以a开始，b结尾（j-1指向的字符为b）没有相同的两个子串，则next[j] = 0,c此时j下标为2.

当j指向第四个字符b时，以a开始，以a(此时j-1指向a）结尾有两个相同的子串（a,a），长度为1，故next[j] = 1,j = 3,以此类推。 解释: 练习二：练习二需要注意的就是求next数组的数字时，查相同子串是可以重叠的，但是一个子串必须以j = 0时开始。

到这里大家对如何求next数组应该问题不大了，接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ? 如果我们能够通过 next[i]的值,通过一系列转换得到 next[i+1]得值，那么我们就能够实现这部分。 那该怎么做呢？ 首先假设： next[i] = k 成立，那么，就有这个式子成立： P0…Pk-1 = Px…Pi-1;得到： P0…Pk-1 = Pi-k…Pi-1; 到这一步：我们再假设如果 Pk = Pi;我们可以得到 P0…Pk = Pi-k…Pi;那这个就是 next[i+1] = k+1;

那么： Pk != Pi 呢？看如下实例：

通过代码理解：

void GetNext(char* sub, int* next,int lenSub)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//当前i下标
	int k = 0;//前一项的k,i-1位置下面的k ，next[1]
	while(i < lenSub)
	{
		if (k == -1 ||sub[i - 1] == sub[k])//k == -1在这判断的原因是防止数组越界
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];//继续回退

		}
	}

}
//str代表主串，sub代表子串，pos代表从主串的pos位置开始找
int KMP(const char* str, const char* sub, int pos)
{
	int lenStr = strlen(str);
	int lenSub = strlen(sub);
	if (lenStr == 0 && lenSub == 0)
		return -1;
	if (pos < 0 || pos >= lenStr)
		return -1;



	int* next = (int*)malloc(sizeof(int) * lenSub);
	assert(next);
	GetNext(sub, next,lenSub);
	int i = pos;//遍历主串
	int j = 0;//遍历子串


	while (i < lenStr && j < lenSub)
	{
		if (j == -1 || str[i] == sub[j])//防止数组越界
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];//j退回到标记的位置
		}
	}
	free(next);
	next = NULL;
	if (j >= lenSub)
	{
		return i-j;
	}
	else
	{
		return -1;
	}
}

int main()
{
	printf("%d\n", KMP("ababcabcdabcde", "abcd", 0));//5
	printf("%d\n", KMP("ababcabcdabcde", "abcdf", 0));//-1
	printf("%d\n", KMP("ababcabcdabcde", "ab", 0));//0
}

总结：

KMP算法只需要在BF算法基础之上改变j的回退步数，并且i不回退，而j的步数则由其对应的next数组的每一个元素存储。