目录

文章目录

前言

一、BF算法

二、KMP算法

1.算法介绍

2.算法思路

 3.整体代码实现

总结

---

前言

字符串匹配算法又称模式匹配算法，该算法的目的是为了子串从主串中寻找是否有与其匹配的部分，

其可分为BF暴力检索、RK哈希检索、KMP、BM等等，本文仅介绍BF算法和KMP算法的实现，前者的时间复杂度是O(mn)，后者的时间复杂度是O(m+n)，本次文章就是对这两者的核心思路进行总结分析，以加强记忆。

---

一、BF算法

算法要求：假设有两个字符串，主串S和子串X，通过BF算法的逐步匹配，找到与子串匹配的主串部分，并返回第一次出现的下标。

算法思路如下：

 代码实现如下（C语言）：

#include<stdio.h>
#include<assert.h>
#include<string.h>

int BF(char* str, char* sub)//str代表主串，sub代表子串
{
	assert(str&&sub);//断言
	if (str == NULL || sub == NULL)//串为空值时直接返回-1
	{
		return -1;
	}
	int i = 0;//遍历主串
	int j = 0;//遍历子串
	int lenstr = strlen(str);//求出主串的长度
	int lensub = strlen(sub);//求出子串的长度
	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//匹配失败，返回-1
		return -1;
}
int main()
{
	printf("%d\n", BF("ababcabcdabcde", "abcd"));//匹配成功，预期返回下标5
	printf("%d\n", BF("ababcabcdabcde", "abcds"));//匹配失败，返回-1
	printf("%d\n", BF("ababcabcdabcde", "ab"));//匹配成功，返回下标0

	return 0;
}

 BF算法缺点：有大量匹配无效，效率低。

二、KMP算法

1.算法介绍

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

2.算法思路

①next数组的求解：

例：有一个字符串ababcabc，求其对应的next数组。

解：第一个字符对应的next数组值为-1，第二个字符对应的next数组值为0，从第三个字符开始，判断第一个字符和第（n-1）个字符中是否有匹配的

数学分析：

假设next[i]=k，可推出p[0]...p[k-1]=p[x]...p[i-1]，既k-1-0=i-1-x，得x=i-k

即p[0]...p[k-1]=p[i-k]...p[i-1]

若能证得p[i]==p[k]，则可求得next[i+1]=k+1。

若p[i]!=p[k]，next[i+1]=??

举个例子：

---

 代码分析：

void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//当前i下标
	int k = 0;//前一项的k

	while(i < lensub)
	{
		if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];//if条件不满足时则需将k回退到-1下标
		}
	}
}

附加知识： next数组的优化（nextval）

同样以例子来讲：

图中所示，当i=5时匹配失败，若按照next数组回退的话，到i=4时，依旧是a，匹配失败还得回退，每次回退都是相同的字符，这些回退无疑是无效的。而nextval数组就是对这一现象的优化。

 3.整体代码实现

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//当前i下标
	int k = 0;//前一项的k

	while(i < lensub)
	{
		if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];//if条件不满足时则需将k回退到-1下标
		}
	}
}

int KMP(char* str, char* sub, int pos)/*str:代表主串；sub:代表子串；pos:代表从主串的pos位置开始找*/
{
	assert(str&&sub);//断言
	if (str == NULL || sub == NULL)//字符串为空直接返回-1
		return -1;
	int lenstr = strlen(str);//求主串长度
	int lensub = strlen(sub);//求子串长度
	if (pos < 0 || pos >= lenstr)//pos位置不合法直接返回-1
		return -1;

	int *next = (int*)malloc(sizeof(int)*lensub);//开辟动态内存给next数组存放数据
	assert(next);

	GetNext(sub, next,lensub);//求出next数组

	int i = pos;//遍历主串
	int j = 0;//遍历子串

	while (i < lenstr&&j < lensub)
	{
		if (j == -1 || str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	next = NULL;
	if (j >= lensub)
	{
		return i - j;
	}
	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
	return 0;
}

总结

以上就是今天要讲的内容，本文介绍了关于字符串匹配的BF算法和KMP算法，通过比特大博哥的视频学习，对算法思路与实现代码进行理解和分析，简单学习记录。欢迎大家探讨指正！