精华内容
下载资源
问答
  • C语言实现BF算法
    2021-05-20 09:41:04

    //头文件

    #include //字符串头文件

    int BF(char s[],char t[],int pos){     //BF算法 s是原字符串,t是匹配字符串

    intm,n;

    inti=pos,j=0;          //从0位置开始匹配

    m=strlen(s);

    n=strlen(t);             //用m,n表示s,t长度

    while (i<=m&&j<=n){               //m,n是串长

    if (s[i]==t[j])

    {

    i++;

    j++;        //逐个匹配,成功s++   t++

    }

    else

    {

    i=i-j+1;       //不成功,s返回到此次循环匹配的初始位置

    j=0;           //不成功,t返回到0位置

    }

    }

    if(j>n)

    return (i-n);          //返回匹配成功的原串中第一个字符的位置

    else

    return 0;

    }

    int main(){

    char s[]="abcdkeabcfgabcde";      //初始定义s串

    int pos;

    pos=BF(s,"abcd",0);        //从0位置匹配abcd

    printf("pos=%d\n",pos);

    pos=BF(s,"abcde",pos);    //从上次匹配成功的位置匹配abcde

    printf("pos=%d\n",pos);

    return0;

    }

    更多相关内容
  • c语言实现BF算法

    2022-04-05 19:17:54
    c语言实现BF算法

    目录

    1.谈谈BF算法实现原理:

    2.看看实现代码:


    1.谈谈BF算法实现原理:

    bf算法是一种比较暴力的算法。适用于查找子串的问题。

    例如:父串(s)为:abbaba 子串(p)为:aba

    核心是:用两个指针(通过下标控制)分别指向s和p。判断指针所指向的值是否相同,若是相同的话,指针同时向后移。不同的话,父串的指针回到匹配成功的下一个位置,子串的指针回到起点。

    直至子串指针走完结束程序。

     关键是:1.匹配成功的下一个位置如何查找?结论:  i=i-j+1;

                 2.结束后的返回值如何计算?结论:    return (i-j);


    2.看看实现代码:

    int BF(char* arr1, char* arr2, int len1, int len2)
    {
    	int i = 0; int j = 0;
    
    	while (i < len1&&j < len2)
    	{
    		if (arr1[i]==arr2[j])//相同则一起后移
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i = i - j + 1;//父串的回溯位置
    			j = 0;//子串回到起始位置
    		}
    	}
    	if (j >= len2)
    		return i - j;
    	else
    		return 0;
    }

    展开全文
  • } //BF算法 int Index_BF(SString& S, SString &T, int pos) { //S是主串,T是模式串,pos是主串开始匹配的位置 int i = pos; int j = 1; while (i) {//循环结束条件就是要么主串没有和模式串匹配的那一段,要么...

    总结
    1.关于数组,我想要一个字符一个字符的输入,没想到直接定义一个有长度的数组,比如ch1=[255],就可以了。输入的时候只要scanf("%s",&ch1),(&好像加不加都可以,不知道为什么。)就可以直接输入了。关于输出我还是不太会,目前先不管。然后把输入的ch1通过函StringAssign(S, ch1)就可以把ch1赋值给S.ch,接着就可以进行匹配了。


    2.串的赋值,是需要函数的。int StringAssign(SString&S, char chs[]);把数组chs里面的元素赋值到S.ch。通过函数可以实现从S.ch[1]开始赋值。

    3.做的时候遇到的问题,就是串的赋值函数,如下:

    int StringAssign(SString&S, char chs[]){//生成一个其值等于字符串常量chs的串S
    	int i = 0;
    	while (chs[i] != '\0'){//循环,将字符串常量的值赋值给S
    		S.ch[i+1] = chs[i];//S.ch数组从下标为1开始存放
    		++i;
    	}
    	S.length = i;//将i赋值给S的长度
    	return 0;
    }

    4.上BF算法的完整可运行代码

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXLEN 255
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    int i, n, j, x;
    char e;
    //顺序存储串
    typedef struct {
    	char ch[MAXLEN + 1];//存储串的一维数组  ch[0]闲置不用,从[1]开始到[255]来存放字符。
    	int length;//串当前长度
    }SString;
    //串赋值
    int StringAssign(SString&S, char chs[]){//生成一个其值等于字符串常量chs的串S
    	int i = 0;
    	while (chs[i] != '\0'){//循环,将字符串常量的值赋值给S
    		S.ch[i+1] = chs[i];//S.ch数组从下标为1开始存放
    		++i;
    	}
    	S.length = i;//将i赋值给S的长度
    	return 0;
    }
    
    
    //BF算法
    int Index_BF(SString& S, SString &T, int pos) {
    	//S是主串,T是模式串,pos是主串开始匹配的位置
    	int i = pos; int j = 1;
    	while (i<=S.length&&j<=T.length) {//循环结束条件就是要么主串没有和模式串匹配的那一段,要么就是匹配成功,j到了模式串最后一位的下一位置
    		if (S.ch[i] == T.ch[j]) {
    			i++;
    			j++;
    		}
    		else {
    			i = i - j + 2;//可以理解为i= (i-j+1)+1,(要先知道,串里面的数组下标为0的地方是不放元素的,所以i是从1开始算起的)
    			//意思就是主串的i回到出发的位置,然后要让i+1,就是让i从开始的位置的下一个位置开始往后匹配。
    			j = 1;//让j回到第一个位置
    		}
    	}
    	if (j > T.length) {//匹配成功
    		printf("\n匹配成功!");
    		printf("\n模式串匹配成功的位置为%d.", i - T.length);
    
    		return OK;//返回的就是模式串的第一个元素的下标(也是位置),因为数组第一位不存元素,所以下标等于位置
    	}
    	else {
    		printf("\n匹配不成功!");
    		return ERROR;
    	}
    }
    int main() {
    	SString S;
    	SString T;
    	char ch1[255];//定义一个数组,等下来放入主串
    	char ch2[255];//放入模式串
    
    	printf("请输入主串:");
    	scanf("%s", &ch1);
    	StringAssign(S, ch1);//引用此函数,可以把数组ch1的元素放进S.ch,作为主串
    	
    	printf("\n请输入模式串:");
    	scanf("%s", &ch2);
    	StringAssign(T, ch2);
    	
    	int pos = 1;//表示从第pos个元素开始查找
    	Index_BF(S, T, pos);//BF算法函数
    	return 0;
    }
    

    展开全文
  • 基于BF和KMP的串模式匹配算法设计与实现(C语言).rar
  • 基于BF和KMP的串模式匹配算法设计与实现(C语言)
  • 【数据结构】BF算法——C语言实现

    千次阅读 2020-05-31 00:19:41
    本文将给大家讲述BF算法C语言实现。 参照严蔚敏版的数据结构中有关BF算法中的不太好理解就是,在发生不匹配的情况下,主串返回的位置为:i-j+2。首先这个可以写成i-(j-1)+1,可以将其理解为:不匹配的主串位置减去...

    BF算法常用于串中的模式匹配,是一个很常见且使用的一种算法。本文将给大家讲述BF算法的C语言实现。
    参照严蔚敏版的数据结构中有关BF算法中的不太好理解就是,在发生不匹配的情况下,主串返回的位置为:i-j+2。首先这个可以写成i-(j-1)+1,可以将其理解为:不匹配的主串位置减去字串匹配滑动的次数在加上一,这样一来主串接收到返回的位置即为起始匹配位置的下一个位置。也许这样说可能还是不太清楚大家可以试着画一个图,去模拟模式匹配的过程。这里还需要指明的是严版的数据结构在BF算法这里做了一个默认,即默认数组是从1开始而非从0开始。
    下面是相关C语言实现的代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAXLEN 255
    
    typedef struct
    {
        char str[MAXLEN];
        int length;
    }SSteing;
    
    int BF(SSteing a,SSteing b,int pos);
    
    int main (void)
    {
        int start = 0; 
        SSteing S,T;
        printf("请输入主串:");
        scanf("%s",S.str);
        printf("请输入子串:");
        scanf("%s",T.str);
        S.length = strlen(S.str);
        T.length = strlen(T.str);
        if(BF(S,T,start))
        {
            printf("yes,起始位置为:%d\n",BF(S,T,start));
        }
        else
        {
            printf("no\n");
        }
        system("pause");
        return 0;
    }
    
    int BF(SSteing a,SSteing b,int pos)
    {
        int i = pos;
        int j = 0;
        while (i <= (a.length-1) && j <= (b.length - 1))
        {
            if(b.str[j] == a.str[i])
            {
                j++;
                i++;
            }
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }
        if(j > (b.length - 1))
        {
            return (i - b.length + 1);
        }
        else
        {
            return 0;
        }
    }
    

    这里我并没有采用数组从1开始而是从0开始,这样的话在匹配失败是返回的位置就要修改为:i-j+1;与书上的不同就在于字串滑动次数的不同,比如:从1位置移动到3位置滑动了(3-1)次,从0位置滑动到2位置滑动了(2-0)=2次。
    如果您有什么见解和疑问欢迎私信我或者通过1308269670@qq.com与我联系。

    展开全文
  • BF算法

    2021-06-20 01:12:33
    BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个...
  • C语言顺序串--BF算法

    2020-10-20 15:44:12
    数据结构C语言静态顺序串 代码如下: #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXSIZE 50 //静态顺序串的最大容纳量 typedef struct { char ch[MAXSIZE];//数据...
  • 主要介绍了c语言中使用BF-KMP算法,大家参考使用
  • 给定一个文本,在该文本中查找并定位任意给定字符串 实现BF算法; 实现BF算法的改进算法:KMP算法和BM算法; 对上述三个算法进行时间复杂性分析,并设计时间程序验证分析结果。
  • Sunday算法c语言版实现

    2021-05-21 04:37:51
    一、BF算法BF算法是普通的模式匹配算法,其基本思想就是将目标串的第一个字符与模式串的第一个字符进行匹配。若相等,则继续比较第二个字符;若不相等,则比较目标串的第二个字符和模式串的第一个字符。依次比较下去...
  • KMP和BF算法-C语言实现

    2021-05-21 04:39:00
    #include #include #include #include //以下为KMP算法void get_next(char * T, int next[]) //修正前的next数组{int i = 1, j = 0;next[0] = -1;next[1] = 0;int m = strlen(T);while (i{if (j == -1 || T[j] == T...
  • BF算法 算法思想: 比较简单,定义i,和j分别指向主串和字串的头部),依次向后比较,若比较失败,主串和字串都需要回溯(i=比较轮数+1的位置,j回到0位置) 元素相同,故i,j均向后移一位 元素不同,i退回第二个...
  • 普通的模式匹配(“BF算法)判断两个串是否存在子串与主串的关系,最直接的算法就是拿着模式串,去和主串从头到尾一一比对,这就是“BF算法的实现思想。将提供的模式串(例如 “abcac” )从主串的第一个字符开始,...
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • C语言》字符串匹配(BF算法+KMP算法)

    千次阅读 多人点赞 2020-05-02 16:07:17
    字符串匹配 【问题描述】 对于字符串S和T,若T是S子串,返回T在S中的位置(T的首字符在S中...采用直接穷举法求解,称为BF算法。该算法从S的每一个字符开始查找,看T是否会出现。例如,S=“aababcde”,T=“abcd”: ...
  • BF算法(暴力匹配) 纯C语言

    千次阅读 2019-04-24 16:06:07
    1.从1开始数的版本(自然语言) #include <...//BF算法 int BF(char s1[20], char s2[20], int pos) { int i = pos - 1;//下标值与自然语言转换 int j = 0; while(i < strlen(s1) &am...
  • 主串与子串:如果串 A(如 "shujujiegou")中包含有串 B(如 "ju"),则称串 A 为主串,串 B 为子串。...BF算法原理普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个串同另一个串中...
  • 串匹配BF算法C语言

    2009-04-29 10:40:48
    最简单的串匹配算法,主串和模式串相比较,若相等,继续逐个后续字符,否则从主串的一下个字符起再重新和模式的字符比较之.
  • BF算法(朴素算法): 说明如下如所示: 实现效果如图: 源码如下: #include<stdio.h> #include<stdlib.h> //结构体 typedef struct String { char* data;//字符串 int len;//长度 }String; /...
  • BF算法和KMP算法是字符串的两种主要的模式匹配算法 1.BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二...
  • 字符的检索是一个非常常用的功能,平时我们使用...所运用的算法为BF算法。 /*子串在目标串首次出现的位置*/ #include<iostream> #include<stdlib.h> #include<string.h> #define MaxSize 100 typedef
  • #include<stdio.h> int length(char *str){ ...int BF(char *txt,char *str){/*返回第一个匹配子串的位置下标*/ int m=length(txt); int n=length(str); for(int i=0;i<=m-n;i++){ in.
  • BF算法 BF(Brute Force)算法又称暴力算法,是一种普通的模式匹配算法,其思想是:从主串第一个字符开始,取子串长度个字符,这些字符分别与子串进行比较,若某位字符不相等,则在主串起始字符向后推移一格与子串再...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,659
精华内容 1,863
关键字:

c语言bf算法设计