BF算法的概念
1.逻辑概念
BF算法又称模式匹配基本算法，该算法的基本思想是，按照自左向右的顺序，从主串的第start个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的第start+1个字符起重新和模式串的字符比较。以此类推，直到模式串t中的每个字符依次和主串s中的一个连续的字符序列相等，则匹配成功，否则匹配失败，下面我们来看BF算法的代码表示
2.代码实现
int Index_String(PString S1,PString S2,int start){ //S1是主串，S2是子串，start是起始位置
int i=start-1,j=0;
while(i<S1->len&&j<S2->len){ //模式匹配
if(S1->data[i]==S2->data[j]){ //当主串元素和子串相等时，继续判断
i++;
j++;
}else{ //只要遇到子串与主串不同的元素，就使主串回到判断起始位置的后一个位置
i=i-j+1; //重新开始匹配
j=0;
}
}
if(j>=S2->len){ //当j大于了子串的长度，说明匹配成功了，返回子串在主串出现的第一个位置
return i-S2->len+1;
}else{ //否则返回0
return 0;
}
}BF算法的应用
1.输出子串在主串中的位置
问题描述
【问题描述】
串的模式匹配算法BF的应用。
【输入形式】
第一行输入主串s；
第二行输入模式串t；
输入串中均不包含空格字符。
【输出形式】
模式串在主串s中的出现的每一个位置序号。若一次都未匹配到，则输出0。
【样例输入1】
ababcabcacbab
ab
【样例输出1】
1 3 6 12
【样例输入2】
111113455113232342432432
11
【样例输出2】
1 2 3 4 10
【样例输入3】
fasdfdsfsadfdsdsagetgrdgfdgdf
2312
【样例输出3】
0
算法思想
对于这个问题，我们使用BF算法来解决的时候，只需要在主函数中循环判断，每次找到一个位置，下次就从该位置后面开始，继续找，直到主串都循环完即可，下面我们来看具体的代码实现
完整代码
这里主要运用了串的初始化，串的赋值以及BF算法
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 10
#define INCREAM 10
typedef struct String{ //结构体
char *data;
int len;
int size;
}String,*PString;
int Init_String(PString S){ //初始化串
S->data=(char *)malloc(sizeof(char)*SIZE);
S->len=0;
S->size=SIZE;
return 1;
}
int Creat_String(PString S,char *s){ //给串赋值（创建串）
int i=0,n;
if(S->size<strlen(s)){ //先判断串的空间是否足够，不够要重新开辟空间
S->data=(char *)realloc(S->data,(S->size+INCREAM)*sizeof(char));
S->size+=INCREAM;
}
n=strlen(s);
for(i=0;i<n;i++){ //给串赋值
S->data[i]=*s++;
}
S->len=n; //最后别忘了串是有长度的
return 1;
}
int Index_String(PString S1,PString S2,int start){ //BF算法
int i=start-1,j=0;
while(i<S1->len&&j<S2->len){
if(S1->data[i]==S2->data[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
if(j>=S2->len){
return i-S2->len+1;
}else{
return 0;
}
}
int Print_String(PString S){ //打印串
int i;
for(i=0;i<S->len;i++){
printf("%c",S->data[i]);
}
printf("\n");
return 1;
}
int main(){
char s1[100],s2[100];
int x;
String S1,S2;
Init_String(&S1);
Init_String(&S2);
gets(s1);
gets(s2);
Creat_String(&S1,s1);
Creat_String(&S2,s2);
x=Index_String(&S1,&S2,1); //我们先看主串有没有子串
if(x==0) printf("0");
while(x!=0){ //当获取到的位置返回值不是0时，继续循环
printf("%d ",x); //打印位置
x=Index_String(&S1,&S2,x+1); //从该位置后面一个位置继续下一次判断
}
return 0;
}运行结果
2.删除主串中的所有子串
问题描述
【问题描述】编写一个程序，当在一个字符串中出现子串时就删除它（字符串的字符个数不超过1000）。
【输入形式】第一行输入一个字符串，第二行输入一个子串。
【输出形式】程序在下一行输出删除其中所有子串后的字符串。如果字符串不包含子串则输出原字符串本身。
【样例输入1】
I am a boy!
a
【样例输出1】
I m boy!
【样例输入2】
Ah Love!could you and I with Fate conspire
ould
【样例输出2】
Ah Love!c you and I with Fate conspire
【样例说明】
删除第一个字符串中所有的子串，包括连续出现的子串。
算法思想
在主串中删除子串，运用BF算法找到子串在主串的位置，然后通过子串的长度，我们执行删除操作，一直循环，直到把子串全部删除为止 ，下面我们来看具体的代码实现
完整代码
这里串的初始化，串的赋值，BF算法都和之前一样，我们具体说一下删除子串的算法
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 10
#define INCREAM 10
typedef struct String{ //结构体
char *data;
int len;
int size;
}String,*PString;
int Init_String(PString S){
S->data=(char *)malloc(sizeof(char)*SIZE);
S->len=0;
S->size=SIZE;
return 1;
}
int Creat_String(PString S,char *s){
int i,n;
n=strlen(s);
for(i=0;i<n;i++){
if(S->size<strlen(s)){
S->data=(char *)realloc(S->data,(S->size+INCREAM)*sizeof(char));
S->size+=INCREAM;
}
S->data[i]=*s++;
}
S->len=n;
return 1;
}
int Index_String(PString S1,PString S2,int start){
int i=start-1,j=0;
while(i<S1->len&&j<S2->len){
if(S1->data[i]==S2->data[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
if(j>=S2->len){
return i-S2->len+1;
}else{
return 0;
}
}
int Print_String(PString S){
int i;
for(i=0;i<S->len;i++){
printf("%c",S->data[i]);
}
return 1;
}
int Delete_String(PString S1,PString S2){ //删除子串的算法
int x;
int i,j;
x=Index_String(S1,S2,1); //先获得一个位置，如果为0，说明主串没有子串，返回0
if(x==0) return 0;
while(x!=0){ //否则，我们执行以下操作
for(i=0;i<S2->len;i++){ //删除主串中的子串
for(j=x-1;j<S1->len-1;j++){ //每次删除一个相同元素，执行次数为子串长度
S1->data[j]=S1->data[j+1];
}
S1->len--; //每删除一个元素，主串长度减少1
}
x=Index_String(S1,S2,1); //重新获取位置，继续执行下一次判断
}
return 1;
}
int main(){
char s1[100],s2[100];
String S1,S2;
Init_String(&S1);
Init_String(&S2);
gets(s1);
gets(s2);
Creat_String(&S1,s1);
Creat_String(&S2,s2);
Delete_String(&S1,&S2);
Print_String(&S1);
return 0;
}运行结果
