字符串匹配算法之BF与KMP算法

BF算法(暴力匹配算法)

KMP算法

核心思想：

next数组

next数组的优化

BF算法(暴力匹配算法)

#include <assert.h>
int BF(const char* str, const char* sub)
{
	assert(str != NULL && sub != NULL);
	if (str == NULL || sub == NULL)
	{
		return -1;
	}
	int i = 0;
	int j = 0;
	int strLen = strlen(str);
	int subLen = strlen(sub);
	while (i < strLen && j < subLen)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;  //主串从上次开始匹配的下一个位置开始匹配
			j = 0; //子串每次从头开始匹配
		}
	}
	if (j >= subLen)
	{
		return i - j; //返回子串在主串中首次出现的首位置的下标
	}
	return -1; //没有匹配返回-1
}

int main()
{
	printf("%d\n", BF("ababcabcdabcde", "abcd")); //5
	printf("%d\n", BF("ababcabcdabcde", "abcde")); //9
	printf("%d\n", BF("ababcabcdabcde", "abcdef")); //-1
	return 0;
}

KMP算法

核心思想：

KMP算法是在BF算法基础上的优化，BF算法中匹配不成功时i和j都要回退，而KMP算法的核心就是匹配失败时，i不回退，而j回退到特定的位置(不一定是0号位置了)，然后继续匹配!

问题:为啥i可以不回退, j也不一定非要回退到0号位置??

有了上面的分析，我们的目标就已经很明确了，就是要计算子串的每个位置匹配失败时，j应该回退到哪一个位置，于是就有了我们的next数组！

next数组

next[i] 记录的就是子串匹配到 i 位置时匹配失败后 i 应该回退的下标

而next数组如何求解呢??? 比如next数组中 i 下标对应的值是几呢??? 那我们只需要看子串中 [0, i-1]这段区间前缀和后缀相等的字符串的最长长度, 假如是k, 那么next[i] = k

子串的第一个位置和第二个位置匹配失败时，该位置之前绝不可能用公共子串，所以next[0]和next[1]都应该是0，但是为了方便后续代码处理，我们将next[0]置成-1

我们现在已经明白了next数组的做用和求法，但问题是上面的next数组是我们肉眼观察求得的，可是计算机并没有上帝视角，如何编程求得next数组呢???

假设已知next[i] = k, 我们能否求得next[i+1]等于多少呢??? 如果可以求出来，由于next[0]和next[1]都是已知的，所以我们只需要从第三个位置开始for循环即可求得next数组~

问题: 已知next[i] = k, 求next[i+1] = 多少??

1.假设p[i] == p[k], 那么next[i+1] = k+1 (p是patten, 指的是子串, 也叫模式串)

证明:

next[i] = k, 说明 p[0] 到 p[k-1] 与 p[x] 到 p[i-1] 这两段字符串是一样的，根据两段字符串长度一样可以求得x, (k-1-0)+1 = (i-1-x)+1, 求得x=i-k, 所以 p[0]...[k-1] == p[i-k]...p[i-1]

而p[i] == p[k], 则 p[0]...[k] == p[i-k]...p[i], 即 next[i+1] = k+1

2.假设p[i] != p[k], 此时需要做的就是让k回退即可，只需要让k = next[k]，一直回退到 p[i] == p[k], 此时next[i+1] = k+1了!!!

如果回退到了0位置，p[i] 仍然不等于 != p[k], k再 = next[k], k就 == -1了，此时如果再判断 p[i] == p[k] 就会越界! 所以如果k == -1了，表明next[i+1]也就是0，刚好是k+1, 这就是为啥把next[0]设置成-1的原因, 然后i++, k++继续填充next数组即可

到此为止，我们就把kmp算法的核心都讲解完了，重点就是kmp算法的核心思想与next数组的原理与求法

#include <assert.h>
#include <stdio.h>
void GetNext(int* next, const char* sub)
{
	int lensub = strlen(sub);
	next[0] = -1;
	next[1] = 0;
	int i = 2;//下一项
	int k = 0;//前一项的K
	while (i < lensub)//next数组还没有遍历完
	{
		//注意，讲解原理时我们假设已知next[i]，求next[i+1], 但写代码时next[i]是我们要求解的，因此已知next[i-1]
		if ((k == -1) || sub[k] == sub[i - 1]) 
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k]; //k回退
		}
	}
}

int KMP(const char* s, const char* sub, int pos) //pos表示从主串的pos位置开始匹配
{
	int i = pos;
	int j = 0;
	int lens = strlen(s);
	int lensub = strlen(sub);
	int* next = (int*)malloc(lensub * sizeof(int));//和子串一样长
	assert(next != NULL);
	GetNext(next, sub);
	while (i < lens && j < lensub)
	{
		if ((j == -1) || (s[i] == sub[j])) 
		{
			i++;
			j++;
		}
		else
		{
			//如果子串的第一个位置字符就和主串不匹配，那么j就会直接变成-1,然后进入if, 此时让j++来到0号位置，i++来到下一个位置继续匹配即可
			j = next[j]; 
		}
	}
	free(next);
	if (j >= lensub)
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}

int main()
{
	const char* str = "ababcabcdabcde";
	const char* sub = "abcd";
	printf("%d\n", KMP(str, sub, 0)); //5
	return 0;
}