BF算法（串的匹配）

BF

BF(Brute Force–野蛮力）
串模式匹配的朴素算法，每次扫描结果不匹配，主串都要回溯，时间复杂度较高：

时间复杂度：O（n*m)

但是实际情况下，由于其复杂度接近于O(n+m),一直沿用。

 //Authors:xiaobei
 
#include<stdio.h> 
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef struct
{
 char ch[MAXSIZE+1];
 int length;
}SString;           //定义串结构 
int Index_BF(SString S,SString T,int pos);
int main()
{
 int pos = 1,pos_i;
 SString S,T;
 printf("
这里是BF算法！
");
 printf("请输入主串)>>>");      //输入主串并获得齐长度、输出 
 gets(S.ch);
 S.length = strlen(S.ch);
 printf("len_S:%d
",S.length);
 puts(S.ch);
 printf("
请输入要匹配子串)>>>");    //输入子串并获得其长度、输出 
 gets(T.ch);
 T.length = strlen(T.ch);
 printf("len_T:%d
",T.length);
 puts(T.ch);
 pos_i = Index_BF(S,T,pos);      //调用函数获得第一次匹配到的位置 
 printf("
匹配的起始位置为:%d",pos_i);
 return 0;
}
int Index_BF(SString S,SString T,int pos)
{
 int i,j;
 i = pos;
 j = 1;
 while(i<=S.length && j<=T.length)    //当检索位置i,j同时小于主串与子串长度时，执行循环 
 {
  if(S.ch[i-1] == T.ch[j-1])
  {
   i++;
   j++;
  }
  else
  {
   i = i-j+2;       //匹配不成功，主串回溯到i-j+2,比较后继字符 
   j = 1;         //匹配不成功，子串回溯到j = 1 
  } 
 }
 if(j>T.length)
  return i-T.length;      //j>T.length匹配成功 
 else
  return 0;        //否则，匹配失败 
}

运行结果：

运行环境：
Dev-C++