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

运行结果