115-串匹配算法的BF方法的实现

Myth丶恋晨 2022-12-30 07:48 96阅读 0赞

## 串匹配算法的BF方法 ##

在一个字符串中查找另一个串的位置  
ababcabcdabcde  
abcd  
搜索引擎 --》 倒排表 标题 --》内容简介 --》URL

![在这里插入图片描述][20201224131349638.png_pic_center]  
接下来是串匹配算法的BF方法的实现

#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;
    }

运行结果如下  
![在这里插入图片描述][20201224131452560.png_pic_center]  
增加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;
    }

运行结果如下  
![在这里插入图片描述][2020122413201439.png_pic_center]  
时间复杂度：最坏情况 O(m\*n)  
但是一般情况下 O(m+n)  
串s的长度为m 串p的长度为n

[20201224131349638.png_pic_center]: /images/20221120/e1d2c55544e9426588e843dab843d858.png
[20201224131452560.png_pic_center]: /images/20221120/303dda4d1ccf4383b79efa553123d4d6.png
[2020122413201439.png_pic_center]: /images/20221120/fd081743135e4d8dab62ad54b75fff90.png