• 中文
    • English
  • 注册
  • 查看作者
  • 字符串的模式匹配之B-F算法

    一.  简介

    字符串的模式匹配问题描述如下:

    设有两个字符串T和Pat,在T中查找是否有和Pat值相等的子串,则称T为目标(Target ),称Pat为模式(Pattern),称查找字符串在目标串中的匹配位置的运算为模式匹配(Pattern matching)

    二. B-F算法

    这个模式匹配方法由Brute 和Force 提出,所以简称为B-F算法,实现原理如下

    字符串的模式匹配之B-F算法

    如果T0 = P0,T1 = P1,T2 = P2,Tm-1 = Pm-1,则匹配成功,返回模式串第0个字符P0在目标串中的匹配的位置

    如果在某个位置i: Ti != Pi,则将模式串Pat右移一位(不是移动位置,只是右移比较),用Pat中字符从头开始与T中字符依次比较

    如此反复执行,若出现以下两种情况之一,则可以结束算法:

    1.   模式串的所有字符都与目标串对应字符相等(匹配成功)
    2.   Pat已经移动到最后可能与T比较的位置,但是依旧没有匹配成功,则返回-1(匹配失败)

    图解如下:

    字符串的模式匹配之B-F算法

    通过上图我们可以得到以下规律:

    • 目标串字符个数 –  模式串字符个数 = 移动次数
    • 移动次数 +  1  =  比较次数
    • 第N次对应了T中的第N个元素
    • 每一次结束进行下一次比较的时候,P都向后移动一个位置,和T中的下一个元素开始依次比较

    三.  代码实现

    #include <stdio.h>
    #include <string.h>
    //for循环的方法解决
    int bf_match(char *t, char *p)
    {
    
        int tlen = strlen(t);
        int plen = strlen(p);
        int i, j;
        for( i = 0; i <tlen - plen + 1; i++)   //只需要比较tlen - plen + 1次
        {
            for(j = 0; j < plen; j++)
            {
                if(t[i + j] != p[j])break;
    
            }
            if(j == plen)
            {
                return i;
            }
        }
        return -1;
    }
    
    //While循环解决
    int bf_match2(char *t,char *p)
    {
        int i =0,j = 0;
        while(t[i] != 0 && p[j] != 0 )  //若t[i]和p[j]都没到结尾则继续执行(因为c语言中字符串的结尾默认添加‘\0’,ASCII码为0)
        {
    
            if(t[i] == p[j])//若相等,分别加1
            {
                i++;  
                j++;
    
            }
            else
            {
                i = i - j + 1;  
                j = 0;
            }
        }
        if(p[j] == 0)
        {
            return i-j;
        }
        else return -1;
    }
    
    int main()
    {
        char *t = "what is your name?";
        char *p = "your";
        int a = bf_match(t,p);
        printf("%d\n",a);
        int b = bf_match2(t,p);
        printf("%d\n",b);
        return 0;
    }
    输出:
    8
    8

     

  • 0
  • 0
  • 0
  • 5.7k
  • XP龙猫

    请登录之后再进行评论

    登录

    赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    单栏布局 侧栏位置: