• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

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

    • 查看作者
    • 字符串的模式匹配之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

       

    • 2
    • 0
    • 0
    • 4.2k
    • XP龙猫

      请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: