加入收藏 | 设为首页 | 会员中心 | 我要投稿 航空爱好网 (https://www.52kongjun.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 综合聚焦 > 编程要点 > 语言 > 正文

BF算法 串模式匹配算法 C语言解说

发布时间:2022-07-07 23:20:56 所属栏目:语言 来源:互联网
导读:串的模式匹配算法,通俗地理解,是一种用来判断两个串之间是否具有主串与子串关系的算法。 主串与子串:如果串 A(如 shujujiegou)中包含有串 B(如 ju),则称串 A 为主串,串 B 为子串。主串与子串之间的关系可简单理解为一个串 包含 另一个串的关系。 实
  串的模式匹配算法,通俗地理解,是一种用来判断两个串之间是否具有"主串与子串"关系的算法。
 
  主串与子串:如果串 A(如 "shujujiegou")中包含有串 B(如 "ju"),则称串 A 为主串,串 B 为子串。主串与子串之间的关系可简单理解为一个串 "包含" 另一个串的关系。
 
  实现串的模式匹配的算法主要有以下两种:
  普通的模式匹配算法;
  快速模式匹配算法;
 
  本节,先来学习普通模式匹配(BF)算法的实现。
  BF算法原理
  普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个串同另一个串中的字符一一比对,得到最终结果。
 
  由此,串 A 与串 B 以供经历了 6 次匹配的过程才成功,通过整个模式匹配的过程,证明了串 A 是串 B 的子串(串 B 是串 A 的主串)。
 
  接下来,我们要编写代码实现两个串的模式匹配(图 1 ~图 4)。
  BF算法实现
  BF 算法的实现思想是:将用户指定的两个串 A 和串 B,使用串的定长顺序存储结构存储起来,然后循环实现两个串的模式匹配过程,C 语言实现代码如下:
  #include <stdio.h>
  #include <string.h>
  //串普通模式匹配算法的实现函数,其中 B是伪主串,A是伪子串
  int mate(char * B,char *A){
      int i=0,j=0;
      while (i<strlen(B) && j<strlen(A)) {
          if (B[i]==A[j]) {
              i++;
              j++;
          }else{
              i=i-j+1;
              j=0;
          }
      }
      //跳出循环有两种可能,i=strlen(B)说明已经遍历完主串,匹配失败;j=strlen(A),说明子串遍历完成,在主串中成功匹配
      if (j==strlen(A)) {
          return i-strlen(A)+1;
      }
      //运行到此,为i==strlen(B)的情况
      return 0;
  }
  int main() {
      int number=mate("ababcabcacbab", "abcac");
      printf("%d",number);
      return 0;
  }
  程序运行结果:
  6
 
  注意,在实现过程中,我们借助 i-strlen(A)+1 就可以得到成功模式匹配所用的次数,也就是串 A 移动的总次数。
  BF算法时间复杂度
  该算法最理想的时间复杂度 O(n),n 表示串 A 的长度,即第一次匹配就成功。
 
  BF 算法最坏情况的时间复杂度为 O(n*m),n 为串 A 的长度,m 为串 B 的长度。例如,串 B 为 "0000000001",而串 A 为 "01",这种情况下,两个串每次匹配,都必须匹配至串 A 的最末尾才能判断匹配失败,因此运行了 n*m 次。

(编辑:航空爱好网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!