字符串的模式匹配是将两个A和B字符串进行比较，如果A字符串是B的子串，那么返回B在A串中出现的位置；如果不是子串，则返回错误。

那么BF算法就是最好想的算法，但是时间复杂度就会大一点。设置两个指针分别指向A和B字符串，如果A指针指向的内容和B指针指向的内容相同的话，A指针和B指针都向后移动并依次比较；如果A指针指向的内容和B指针指向的内容不同的话，A指针向后移动，B指针不发生变动再依次进行比较。

下面我们来实现这个算法：

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    char*ch;
    int length;
    int capacity;//顺序表
}ST;
int indexBF(ST S,ST T,int pos){
    int i=pos,j=1;
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else{
            i=i-j+1;//i返回原先的下一个位置
            j=1;
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}
void Init(ST*p){
    p->ch=NULL;
    p->size=0;
    p->capacity=0;
}
void checkcapacity(ST*p){
    if(p->size==p->capacity){
        char newcapacity=p->capacity==0?4:p->capacity*2;
        char*tmp=(char*)realloc(p->ch,newcapacity*2*sizeof(char));
        if(tmp==NULL)
            exit(0);
        else{
            p->ch=tmp;
            p->capacity=newcapacity;
        }
    }
}
void input(ST*p){
    checkcapacity(p);
    char x;
    printf("请输入字符：");
    while(scanf("%c",&x)!='\n'){
        p->ch[p->size]=x;
        p->size++;
    }
}
void Print(ST*p){
    int i;
    for(i=0;i<p->size;i++)
        printf("%c ",p->ch[i]);
}
int main(){
    ST S,T;
    init(&S);
    init(&T);
    printf("请输入源字符串：");
    Input(&S);
    printf("请输入模式串：");
    Input(&T);
    Print(&S);
    Print(&T);
    printf("子串开始位置是：%d\n",indexBF(S,T,0));
    return 0;
}