637-字符串模式匹配-BF算法

水深无声 2022-09-12 07:55 157阅读 0赞

**字符串模式匹配**  
模式串(或子串)在主串中的定位操作通常称为串的模式匹配，它是各种串处  
理系统中最重要的运算之一。

## BF算法 ##

**布鲁特-福斯算法**  
从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐个字  
符进行后续比较，否则从主串的第二个字符起与模式串的第一个字符重新开始比较，直至模式串中每个字符依次与主串中的一个连续的字符序列相等时为止，此时称为匹配成功；如果在主串中不存在与模式串相同的子串，则匹配失败。

## 图解过程 ##

**给定主串“ABCDABCDABBABCDABCDABDD”，子串“ABCDABD”**  
1、第一趟比较，先比较 A，然后是 BCDAB。  
![在这里插入图片描述][08972dc4aa474ad0b21e96b828586e3f.png]  
在比较最后一个字符 D 时，不匹配。  
![在这里插入图片描述][4ed466e4db9545ffaf889cd65ebf893a.png]  
2、第二趟比较，主串回退到比前一趟加 1 的位置。子串从 0 开始。第一个就不匹配。结束本趟。  
![在这里插入图片描述][b874799929cd47c5b7b14fc484bde1a0.png]  
3、第三趟比较，主串回退到比前一趟加 1 的位置，子串从 0 开始。第一个还是不匹配。同样结束本趟。  
![在这里插入图片描述][ce2d175603254fdbb95cf1787aaa8430.png]  
……  
i、第 i 趟比较，找到可以匹配的子串  
![在这里插入图片描述][40c07eb06e0541c8b74a524336c44460.png]

/****************************************************************
     * 函数名称：searchFS
     * 功能描述：布鲁特-福斯模式匹配
     * 参数说明：src, 主串
     *			sub, 模式串
     * 返 回 值：-1,表示不成功，非0的值表示模式串sub在主串src的位置
    *****************************************************************/
    int searchFS(const char *src, const char*sub)
    {
        
    	int i, j;
    	i = 0;
    	j = 0;
    	int strLen = strlen1(src);
    	int tLen = strlen1(sub);
    	while (i<strLen && j<tLen)
    	{
        
    		if (src[i] == sub[j])
    		{
        
    			++i;
    			++j;
    		}
    		else
    		{
        
    			//主串回退
    			i = i - j + 1;
    			//子串
    			j = 0;
    		}
    	}
    	if (j >= tLen)
    	{
        
    		return (i - tLen);
    	}
    	return -1;
    }
    
    int searchFS(const char *src, const char*sub, int pos)
    {
        
    	int i, j;
    	i = pos;
    	j = 0;
    	int strLen = strlen1(src);
    	int tLen = strlen1(sub);
    	while (i<strLen && j<tLen)
    	{
        
    		if (src[i] == sub[j])
    		{
        
    			++i;
    			++j;
    		}
    		else
    		{
        
    			//主串回退
    			i = i - j + 1;
    			//子串
    			j = 0;
    		}
    	}
    	if (j >= tLen)
    	{
        
    		return (i - tLen);
    	}
    	return -1;
    }
    
    
    /****************************************************************
     * 函数名称：searchFSAll
     * 功能描述：查找模式串在主串中所有的出现的位置
     * 参数说明：locArr, 位置的数组
     *			src, 主串
     *			sub, 模式串
     * 返 回 值：0,表示没有匹配的，非值，表示有匹配的个数
    *****************************************************************/
    int searchFSAll(int locArr[],const char *src, const char *sub)
    {
        
    	//调用
    	int i = 0;
    	int srcLen = strlen1(src);
    	int subLen = strlen1(sub);
    	//int res = searchFS(src, sub, 0);
    	//if (res != -1)
    	//{//找到了 , res是当前的一个位置 （排除 ABABACDABAC   ABA）
    	//	//记录res
    	//	locArr[i] = res;
    	//	i++;
    	//	res += subLen;
    	//	res = searchFS(src, sub, res);
    	//}
    
    	int res = 0;
    	int bj = 0;
    	while ((res = searchFS(src, sub, res)) != -1)
    	{
        
    		++bj;//表示找到一个，加1
    		locArr[i] = res;
    		i++;
    		res += subLen;
    	}
    
    	return bj;
    }

## 代码实现 ##

#include<stdio.h>
    #include<string.h> 
    
    int BF(const char*s,const char*p)
    {
        
    	int lens=strlen(s);
    	int lenp=strlen(p);
    	
    	if(s==NULL||p==NULL||lenp>lens) return -1;
    	
    	int i=0;
    	int j=0;
    	while(i<lens&&j<lenp)
    	{
        
    		if(s[i]==p[j])
    		{
        
    			i++;
    			j++;
    		}
    		else
    		{
        
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(j==lenp)
    	{
        
    		return i-j;
    	}
    	return -1;
    	
    }
    
    int main()
    {
        
    	const char *s="ababcabcdabcde";
    	const char *p="abcd";
    	
    	printf("%d\n",BF(s,p));
    	return 0;
    }

![在这里插入图片描述][543d1f99282f4ef98d6ba12df841d7cd.png]

**增加pos位置的方法**

#include<stdio.h>
    #include<string.h> 
    
    int BF(const char*s,const char*p,int pos)
    {
        
    	int lens=strlen(s);
    	int lenp=strlen(p);
    	
    	if(s==NULL||p==NULL||lenp>lens) return -1;
    	
    	int i=pos;
    	int j=0;
    	while(i<lens&&j<lenp)
    	{
        
    		if(s[i]==p[j])
    		{
        
    			i++;
    			j++;
    		}
    		else
    		{
        
    			i=i-j+1;
    			j=0;
    		}
    	}
    	if(j==lenp)
    	{
        
    		return i-j;
    	}
    	return -1;
    	
    }
    
    int main()
    {
        
    	const char *s="ababcabcdabcde";
    	const char *p="abcd";
    	
    	printf("%d\n",BF(s,p,6));
    	return 0;
    }

## 性能分析 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

[08972dc4aa474ad0b21e96b828586e3f.png]: /images/20220828/b01d8cba7b7b48abadb19b76357f9950.png
[4ed466e4db9545ffaf889cd65ebf893a.png]: /images/20220828/dd7c7210a3bf4790ad9611a66c42965f.png
[b874799929cd47c5b7b14fc484bde1a0.png]: /images/20220828/4e2ffb8702e946a5a75e327254dc6a54.png
[ce2d175603254fdbb95cf1787aaa8430.png]: /images/20220828/08e5d7daf20b4f84a82bfd6427d619af.png
[40c07eb06e0541c8b74a524336c44460.png]: /images/20220828/d27d7278078c4c5a8f66dc347c89ab08.png
[543d1f99282f4ef98d6ba12df841d7cd.png]: /images/20220828/85b59affdb1e4826ba68c2ceff7cfe8f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5670dc765aec45058e6ffe830bca28f7.png