目录

1.谈谈BF算法实现原理:

2.看看实现代码:

1.谈谈BF算法实现原理:

bf算法是一种比较暴力的算法。适用于查找子串的问题。

例如：父串（s）为:abbaba 子串（p）为:aba

核心是:用两个指针（通过下标控制）分别指向s和p。判断指针所指向的值是否相同，若是相同的话，指针同时向后移。不同的话，父串的指针回到匹配成功的下一个位置，子串的指针回到起点。

直至子串指针走完结束程序。

 关键是:1.匹配成功的下一个位置如何查找?结论：  i=i-j+1;

             2.结束后的返回值如何计算?结论:    return (i-j);

2.看看实现代码:

int BF(char* arr1, char* arr2, int len1, int len2)
{
	int i = 0; int j = 0;

	while (i < len1&&j < len2)
	{
		if (arr1[i]==arr2[j])//相同则一起后移
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;//父串的回溯位置
			j = 0;//子串回到起始位置
		}
	}
	if (j >= len2)
		return i - j;
	else
		return 0;
}

总结
1.关于数组，我想要一个字符一个字符的输入，没想到直接定义一个有长度的数组，比如ch1=[255],就可以了。输入的时候只要scanf("%s",&ch1)，（&好像加不加都可以，不知道为什么。）就可以直接输入了。关于输出我还是不太会，目前先不管。然后把输入的ch1通过函StringAssign(S, ch1)就可以把ch1赋值给S.ch，接着就可以进行匹配了。

2.串的赋值，是需要函数的。int StringAssign(SString&S, char chs[]);把数组chs里面的元素赋值到S.ch。通过函数可以实现从S.ch[1]开始赋值。

3.做的时候遇到的问题，就是串的赋值函数，如下：

int StringAssign(SString&S, char chs[]){//生成一个其值等于字符串常量chs的串S
	int i = 0;
	while (chs[i] != '\0'){//循环，将字符串常量的值赋值给S
		S.ch[i+1] = chs[i];//S.ch数组从下标为1开始存放
		++i;
	}
	S.length = i;//将i赋值给S的长度
	return 0;
}

4.上BF算法的完整可运行代码

#include<stdio.h>
#include<stdlib.h>
#define MAXLEN 255
#define OK 1
#define ERROR 0
#define OVERFLOW -2
int i, n, j, x;
char e;
//顺序存储串
typedef struct {
	char ch[MAXLEN + 1];//存储串的一维数组  ch[0]闲置不用，从[1]开始到[255]来存放字符。
	int length;//串当前长度
}SString;
//串赋值
int StringAssign(SString&S, char chs[]){//生成一个其值等于字符串常量chs的串S
	int i = 0;
	while (chs[i] != '\0'){//循环，将字符串常量的值赋值给S
		S.ch[i+1] = chs[i];//S.ch数组从下标为1开始存放
		++i;
	}
	S.length = i;//将i赋值给S的长度
	return 0;
}


//BF算法
int Index_BF(SString& S, SString &T, int pos) {
	//S是主串，T是模式串，pos是主串开始匹配的位置
	int i = pos; int j = 1;
	while (i<=S.length&&j<=T.length) {//循环结束条件就是要么主串没有和模式串匹配的那一段，要么就是匹配成功，j到了模式串最后一位的下一位置
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;//可以理解为i= (i-j+1)+1,（要先知道，串里面的数组下标为0的地方是不放元素的，所以i是从1开始算起的）
			//意思就是主串的i回到出发的位置，然后要让i+1,就是让i从开始的位置的下一个位置开始往后匹配。
			j = 1;//让j回到第一个位置
		}
	}
	if (j > T.length) {//匹配成功
		printf("\n匹配成功！");
		printf("\n模式串匹配成功的位置为%d.", i - T.length);

		return OK;//返回的就是模式串的第一个元素的下标（也是位置），因为数组第一位不存元素，所以下标等于位置
	}
	else {
		printf("\n匹配不成功！");
		return ERROR;
	}
}
int main() {
	SString S;
	SString T;
	char ch1[255];//定义一个数组，等下来放入主串
	char ch2[255];//放入模式串

	printf("请输入主串：");
	scanf("%s", &ch1);
	StringAssign(S, ch1);//引用此函数，可以把数组ch1的元素放进S.ch,作为主串
	
	printf("\n请输入模式串：");
	scanf("%s", &ch2);
	StringAssign(T, ch2);
	
	int pos = 1;//表示从第pos个元素开始查找
	Index_BF(S, T, pos);//BF算法函数
	return 0;
}

BF算法常用于串中的模式匹配，是一个很常见且使用的一种算法。本文将给大家讲述BF算法的C语言实现。
参照严蔚敏版的数据结构中有关BF算法中的不太好理解就是，在发生不匹配的情况下，主串返回的位置为：i-j+2。首先这个可以写成i-(j-1)+1，可以将其理解为：不匹配的主串位置减去字串匹配滑动的次数在加上一，这样一来主串接收到返回的位置即为起始匹配位置的下一个位置。也许这样说可能还是不太清楚大家可以试着画一个图，去模拟模式匹配的过程。这里还需要指明的是严版的数据结构在BF算法这里做了一个默认，即默认数组是从1开始而非从0开始。
下面是相关C语言实现的代码：

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

#define MAXLEN 255

typedef struct
{
    char str[MAXLEN];
    int length;
}SSteing;

int BF(SSteing a,SSteing b,int pos);

int main (void)
{
    int start = 0; 
    SSteing S,T;
    printf("请输入主串：");
    scanf("%s",S.str);
    printf("请输入子串：");
    scanf("%s",T.str);
    S.length = strlen(S.str);
    T.length = strlen(T.str);
    if(BF(S,T,start))
    {
        printf("yes，起始位置为：%d\n",BF(S,T,start));
    }
    else
    {
        printf("no\n");
    }
    system("pause");
    return 0;
}

int BF(SSteing a,SSteing b,int pos)
{
    int i = pos;
    int j = 0;
    while (i <= (a.length-1) && j <= (b.length - 1))
    {
        if(b.str[j] == a.str[i])
        {
            j++;
            i++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if(j > (b.length - 1))
    {
        return (i - b.length + 1);
    }
    else
    {
        return 0;
    }
}

这里我并没有采用数组从1开始而是从0开始，这样的话在匹配失败是返回的位置就要修改为：i-j+1；与书上的不同就在于字串滑动次数的不同，比如：从1位置移动到3位置滑动了（3-1）次，从0位置滑动到2位置滑动了（2-0）=2次。
如果您有什么见解和疑问欢迎私信我或者通过1308269670@qq.com与我联系。