字符串：BF算法

爱被打了一巴掌 2022-06-01 11:46 180阅读 0赞

# BF算法介绍 #

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

# BF算法分析 #

**算法思想很简单，就是子串的第一位可主串进行比较，如果相等，然后下一位进行比较，遇到不相等，主串从开始比较的哪一位的下一位和子串第一位进行比较，直到出现匹配结果。**写法有很多种，只要思想ok，就可以写出来。

# 代码展示 #

下面采用c语言进行实现，函数返回的是子串在主串中的index。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    
    int IndexSubString(char* dest_str,char* sub_str,int begin)
    {
    	if (begin < 0)
    	{
    		begin = 0;
    	}
    	char* dest = dest_str + begin;
    	char* sub = sub_str;
    	//通过字符一个一个进行比较
    	while (*dest != 0)
    	{
    		//和子串第一个字符不相等
    		if (*dest != *sub)
    		{
    			dest++;
    			continue;
    		}
    		char* temp = dest;
    		//走到这里主串和子串第一个字符相等，继续往下进行比较
    		sub++;
    		dest++;
    		//遇到不相等的字符就回溯，主串回溯到标记的下一位继续和子串的第一位开始进行比较
    		while (*sub != 0)
    		{
    			if (*sub == *dest)
    			{
    				sub++;
    				dest++;
    			}
    			else
    			{
    				sub = sub_str;
    				dest = temp + 1;
    				break;
    			}
    		}
    		//判断子串是否遍历完毕,返回位置
    		if (*sub == 0)
    		{
    			return dest - dest_str - strlen(sub_str);
    		}
    	}
    	return -1;
    }
    
    
    //brute force BF算法又称，暴风算法，普通的模式匹配算法
    int main_BF(int argc, char *argv[])
    {
    	char dest[100] = { 0 }, sub[100] = { 0 }, num[5] = {0};
    	int begin = 0;
    	while (1)
    	{
    		memset(dest, 0, 100);
    		memset(sub, 0, 100);
    		memset(num, 0, 5);
    
    		printf("请输入目标字符串(#退出):");
    		fgets(dest, 100, stdin);
    		dest[strlen(dest)-1] = 0;//去掉换行符
    		if (strcmp(dest,"#")==0)
    		{
    			break;
    		}
    
    		printf("请输入查询起始位置(不输入从0开始):");
    		fgets(num, 5, stdin);
    		if (strlen(num) != 1)
    		{
    			num[strlen(num) - 1] = 0;//去掉换行符
    			sscanf(num, "%d", &begin);
    		}
    
    
    		printf("请输入查询子串:");
    		fgets(sub, 100, stdin);
    		sub[strlen(sub) - 1] = 0;//去掉换行符
    
    		int index = IndexSubString(dest, sub, begin);
    		printf("dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin,index);
    	}
    
    	return 0;
    }

# 运行检测 #

![Center][]

[Center]: /images/20220601/6b0a5b3dbd4b478d9fa8692ac396a0d4.png