BF算法

//200624101101杨振平
#include <stdio.h>
//全局变量计算比较次数
int count=0;
//主函数
void main()
{
 //声明BF算法的函数原型
 int BF(char S[],int n,char T[],int m);
 //初始化主串
 char S[14]="ababcabcacbab";
 printf("主串:%s/n",S);
 //初始化子串
 char T[6]="abcac";
 printf("子串:%s/n",T);
 //输出匹配结果
 printf("串匹配位置:%d/n",BF(S,13,T,5));
 printf("串匹配比较次数:%d/n",count);
}
//定义实现BF算法的函数
int BF(char S[],int n,char T[],int m)
{
 int i=0;
 int j=0;
 while(i<n && j<m)
 {
  if(S[i]==T[j] && ++count)
  {
   i++;
   j++;
  }
  else
  {
   i=i-j+1;
   j=0;
  }
 }
 if(j<=m)
  return i-j+1;
 else
  return 0;
}

时间: 2024-10-23 02:13:24

BF算法的相关文章

模式匹配:从BF算法到KMP算法

模式匹配 子串的定位操作通常称为串的模式匹配.模式匹配的应用很常见,比如在文字处理软件中经常用到的查找功能.我们用如下函数来表示对字串位置的定位: int index(const string &Tag,const string &Ptn,int pos) 其中,Tag为主串,Ptn为子串(模式串),如果在主串Tag的第pos个位置后存在与子串Ptn相同的子串,返回它在主串Tag中第pos个字符后第一次出现的位置,否则返回-1. BF算法 我们先来看BF算法(Brute-Force,最基本

大话数据结构十:字符串的模式匹配(BF算法)

1. BF算法简介: BF(Brute Force)算法是普通的模式匹配算法,又称为朴素匹配算法或蛮力算法,该算法最大缺点就是字符匹配失败指针就要回溯,所以性能很低. 2. BF算法思想: 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符

python通过BF算法实现关键词匹配的方法_python

本文实例讲述了python通过BF算法实现关键词匹配的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: #!/usr/bin/python # -*- coding: UTF-8 # filename BF import time """ t="this is a big apple,this is a big apple,this is a big apple,this is a big apple." p="apple&q

串模式匹配BF算法的java实现

问题描述 串模式匹配BF算法的java实现 如下代码,进行串模式匹配BF算法的java实现 class BF{ public int bF(char S[],char T[]){ int i=0,j=0,index=0; while(S[i]!=''&&T[j]!=''){ if(S[i] == T[j]){ i++; j++; }else{ index++; i = index; j = 0; } } if(T[j]!=''){ return index+1; }else{ return

字符串的模式匹配详解--BF算法与KMP算法_C 语言

一.BF算法    BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果.    举例说明: S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcab

JavaScript中数据结构与算法(四):串(BF)

  这篇文章主要介绍了JavaScript中数据结构与算法(四):串(BF),串是由零个或多个字符组成的有限序列,又叫做字符串,本文着重讲解了BF(Brute Force)算法,需要的朋友可以参考下 串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的.线性表更关注的是单个元素的操作CURD,串则是关注查找子串的位置,替换等操作. 当然不同的高级语言对串的基本操作都有不同的定义方法,但是总的来说操作的本质都

JavaScript中数据结构与算法(四):串(BF)_javascript技巧

串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的.线性表更关注的是单个元素的操作CURD,串则是关注查找子串的位置,替换等操作. 当然不同的高级语言对串的基本操作都有不同的定义方法,但是总的来说操作的本质都是相似的.比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等 这里主要讨论下字符串模式匹配的几种经典的算法:BF.BM

JavaScript中数据结构与算法(五):经典KMP算法

  这篇文章主要介绍了JavaScript中数据结构与算法(五):经典KMP算法,本文详解了KMP算法的方方面在,需要的朋友可以参考下 KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上

KMP算法(转)

 KMP算法         在介绍KMP算法之前,先介绍一下BF算法. 一.BF算法     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果.     举例说明:     S:  ababcababa     P:  ababa  BF算法匹配的步骤如下            i=0