【数据结构】字符串匹配(BF KMP)算法

2021/10/28 11:10:35

本文主要是介绍【数据结构】字符串匹配(BF KMP)算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在开始前需要了解子串和真子串的区别

abc  的  子串有 a  ,b,c,ab,bc,ac,abc  ,  而真子串是不包括自身的其他子串

BF算法  

目的 : 在主串中 ,找到子串开始的位置 

如  主串  aaaabaa   子串 ab      就应该返回下标3

BF算法的思想是 :1让主串和子串一一比较 ,主串下标记作i  子串下标记作j   让i++  j++

2  如果j 走出了范围就说明 找到了子串 ,  返回 i -j (因为要返回起始位置 ,主串走过的长度就是i)

3  如果 i  和 j 不相等,就让 j =0  , i 回退到这一趟 开始下标的下一个位置 (i-j+1),如果这里的 i 不回退的话,有可能跳过子串  。

如 主串是 aaabaaaa  子串是 aab  , 应该返回的是 1 下标 ,但 如果没有回退 i 的话 , 开始比较 到 2 号下标不相等  i 又从 2下标开始比较 ,跳过了主串 。所以需要回退i 。

以上就是 BF算法的主要思想 , 下来实现一下 代码 。

int BF_Search(const char *str, const char *sub, int pos)//pos代表主串开始查找的下标位置
{
	assert(str!=NULL && sub!=NULL);
	if(pos<0 || pos>=(int)strlen(str))
	{
		//return -1;
		pos = 0;
	}

	int len_str = strlen(str);//主串的长度信息
	int len_sub = strlen(sub);//子串的长度信息
	int i = pos;//主串开始位置
	int j = 0;//子串开始位置

	while(i<len_str && j<len_sub)
	{
		if(str[i] == sub[j])//如果相等,两者同时向后走,i++,j++
		{
			i++;
			j++;
		}
		else//不相等  i回退到i-j+1    j回退开始位置0
		{
			i = i-j+1;//i-j是这一趟的开始位置    这一趟的下一个位置:i-j+1
			j = 0;
		}
	}

	//此时while循环退出   两种情况,要么i走出范围   要么j走出范围
	if(j >= len_sub)//如果子串的j走出范围,找到了,返回i-j
	{
		return i-j;
	}
	else//否则没有找到,匹配失败,返回-1
	{
		return -1;
	}
}

BF算法的问题效率太低 , 时间复杂度是O(n*m) 

效率低主要是因为 i  进行了太多次无效的回退 

 如 主串是 abcbcababcd ,子串是abcd ,这种情况下 ,在3 下标发生失配 ,还有必要让 i 回退到 1 下标吗 ,在子串各个字母不相等的情况下是没必要让 i 进行回退的 , 因为 对 abcd 来说 不管在哪个下标发生失配 前面相等的部分都跟第一个下标 a 不相等 , 回退都是无效操作 。

或者主串是 abcabdabdabcabc   ,  子串是abcabc, 在5 下标发生失配时 ,i 回退到b或者c 都是浪费时间的操作 ,因为和子串第一个字符都不相等 , 回退到 3 下标a 才算有效回退。

根据以上思路就有了KMP 算法

KMP 算法的核心思想是不让 i  回退

如果是第一种情况子串的字符互不相等 , 让 i ++ ,j ++ ,发生失配时 j =0 就可

重点是第二种情况子串有相等的字符,如何不让 i 回退 :对于 abcabdabdabcabc 和  abcabc 来说 ,i 在5 号下标发生失配 ,而它的合适回退位置是3下标 , 但仔细观察发现 3和4下标 和子串的前两个字符都相等,如果我们让 j 直接回退到 3 下标开始 那 i 就不用回退了。

我们把 j 回退的合适位置记作 k  ,让 j 每次回退到合适位置 k 代替 i 的回退。而对于子串来说 , j有可能在任何位置发生失配 ,所以每个位置都要有一个合适回退位置 k 。定义一个next数组来记录k 。

找k 的方法 : 发生失配位置向前看,看子串中是否存在两个相等真子串,一个顶头一个顶尾,如果存在 ,k 就是这个真子串的长度。

因为前两个字符都不存在两个真子串 , 所以前两个k是固定的 -1和0 , 对于abcabc来说 它的next是 { -1,0,0,0,1,2} 。

如何理解找 k 的方法呢 ,找 k 的目的是让 j 代替 i  的回退 ,如果没有 k  就是让 i 退到有效适配的位置 ,让 j 退到 0进行比较 , 而 i 到有效适配中间的字符 就是 j  发生失配位置 之前的后半段 ,所以找顶头和顶尾的真子串 ,如果没有的话 那 j 失配位置的后半段 必定不和前半段相等 ,这个时候k 就是0 ,如果有相等的真子集 , 那 i 回退的那一段 就和 j 顶头的子集相等 ,所以让 j 从相等之后开始 就可以代替 i 的回退。

比如有子串 ababcababcaba  ,如果是 4 下标 c 发生失配 ,对于主串来说应该回退到 3下标 a位置是有效回退 , 而 i  回退的位置 ab 又和 子串开始的ab 相等 ,所以让 i 不会退的话 , j 应该回退到 2下标。

//专门针对子串获取其next数组
int *Get_next(const char *sub)
{
	//assert
	int len_sub = strlen(sub);
	int *next = (int*)malloc(sizeof(int) * len_sub);
	assert(next != 0);

	next[0] = -1;
	next[1] = 0;

	int j = 1;
	int k = 0;

	//通过已知推位置  j是已知  则j+1是未知     
	while(j+1 < len_sub)//未知位置需要合法  所以做了一个判断
	{
		if(sub[j] == sub[k] || (k==-1))//要么相等k++赋值,要么不相等k一直回退,触发了保底机制(k==-1)
		{
			//next[++j] = ++k;
			k++;
			j++;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}

	return next;
}




int KMP_Search(const char *str, const char *sub, int pos)//pos代表主串开始查找的下标位置
{
	assert(str!=NULL && sub!=NULL);
	if(pos<0 || pos>=(int)strlen(str))
	{
		//return -1;
		pos = 0;
	}

	int len_str = strlen(str);//主串的长度信息
	int len_sub = strlen(sub);//子串的长度信息
	int i = pos;//主串开始位置
	int j = 0;//子串开始位置

	
	int *next = Get_next(sub);

	while(i<len_str && j<len_sub)
	{
		if((j==-1) || str[i] == sub[j])//如果相等,两者同时向后走,i++,j++
		{
			i++;
			j++;
		}
		else//不相等  i回退到i-j+1    j回退开始位置0
		{
			//i不回退
			j = next[j];//next[j] == k
		}
	}

	//此时while循环退出   两种情况,要么i走出范围   要么j走出范围
	if(j >= len_sub)//如果子串的j走出范围,找到了,返回i-j
	{
		return i-j;
	}
	else//否则没有找到,匹配失败,返回-1
	{
		return -1;
	}
}



这篇关于【数据结构】字符串匹配(BF KMP)算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程