PTA 串的算法设计 5 BF匹配算法（单次匹配）

作者 张鏖烽

单位 湖南工程学院

设计一个简单匹配算法（BF匹配算法）BF_Match(SqString *s,SqString *t):匹配模式串t在目标串s中的位置，匹配成功返回开始的位置，否则返回-1；

函数接口定义：

int BF_Match(SqSteing *s,SqString *t);//匹配模式串t在目标串s中的位置；

其中t为模式串，s为目标串；

裁判测试程序样例：

#include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef struct{ char data[MaxSize]; int length; }SqString; void Init_SqStr(SqString *&s) { s=(SqString *)malloc(sizeof(SqString)); s->length=0; } void Create_SqStr(SqString *&s,char cstr[]) { int i; for(i=0;cstr[i]!='\0';i++) s->data[i]=cstr[i]; s->length=i; } int BF_Match(SqString *s,SqString *t); int main() { char cstr[MaxSize]; int i; SqString *s,*t; Init_SqStr(s); Init_SqStr(t); scanf("%s",cstr); Create_SqStr(s,cstr); scanf("%s",cstr); Create_SqStr(t,cstr); i=BF_Match(s,t); if(i==-1) printf("匹配失败！"); else printf("匹配成功！模式串t在目标串s中开始的位置为：%d",i); return 0; } /* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

bacdabcdefgh abcde

输出样例：

在这里给出相应的输出。例如：

匹配成功！模式串t在目标串s中开始的位置为：4

参考代码：

int BF_Match(SqString*s,SqString*t){ int i=0,j=0; while(i<s->length&&j<t->length){ if(s->data[i]==t->data[j]){ i++;j++; }else{ i=i-j+1; j=0; } } if(j==t->length){ return i-j; }else{ return -1; } }