字符串匹配算法（BF、KMP)

目录

1、暴力匹配（BF）算法

2、KMP算法

---

1、暴力匹配（BF）算法

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

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

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

 代码：

#include 
#include 
#include 
//str 主串
//sub 子串
//如果找到了，返回子串在主串中的下标，否则，返回-1
int BF(char* str, 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;
	}
	//如果主串走到空，证明主串里没有子串
	return -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;
}

2、KMP算法

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

区别：KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且 j 也不会移动到 0 号位置 

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

1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1下标字符结尾。

2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始（next[0]也可以是0，只需要在写代码的时候控制好就可以了）。

求next数组：找到两个相等的字符串，第一个串必须以0下标的字母开头，第二个串必须以下标为j-1（j为目标字符）的字母结尾，这串相等的字符串的长度就是目标字母next数组的值。

例1：对于”ababcabcdabcde”， 求其的 next 数组？

 例2：”abcabcabcabcdabcde”,求其的 next 数组？

 对此，我们对next数组是什么也有了一定的了解。根据观察，我们发现当p[i]==p[k]时（p为字符串），next数组会递增，那么如何证明呢？

接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ?

如果我们能够通过 next[i]的值,通过一系列转换得到 next[i+1]得值，那么我们就能够实现这部分。

 代码：

#include
#include
#include
 
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数组还没有遍历完
	{
		if ((k == -1) || sub[k] == sub[i - 1])//
		{
			next[i] = k + 1;
			i++;
			k++;//k = k+1下一个K的值新的K值
		}
		else
		{
			k = next[k];
		}
	}
}
int KMP(const char* s, const char* sub, int 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 = next [j];
		}
	}
	free(next);
	if (j >= lensub)
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}
int main()
{
	char* str = "ababcabcdabcde";
	char* sub = "abcd";
	printf("%d\n", KMP(str, sub, 0));
	return 0;
}

next数组的优化 

next 数组的优化，即如何得到 nextval 数组：有如下串： aaaaaaaab,他的 next 数组是-1,0,1,2,3,4,5,6,7. 而修正后的数组 nextval 是： -1， -1， -1， -1， -1， -1， -1， -1， 7。为什么出现修正后的数组，假设在 5 号处失败了，那退一步还是 a，还是相等，接着退还是 a。

 

nextval数组的求法很简单，如果当前回退的位置，正好是和当前字符一样，那么就写那个字符的nextval值。不一样就写自己的。

如上面例子中：4的下标字符a，应该回退到下标为1位置，下标为1位置不是a.所以，nextval值，就是当前next值。
比如5的下标字符b，应该回退到下标为1位置，下标为1位置也是b.那么此时的nextval值，就是1下标b的nextval值。

优化后得到next数组代码：

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)
	{
		if ((k == -1) || sub[k] == sub[i - 1])
		{
			
			if (sub[i] == sub[k])//当两个字符相同时，就跳过
				next[i] = next[k];
			else
				next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}