【数据结构与算法】字符串匹配 BM算法

深碍√TFBOYSˉ_ 2022-12-01 01:18 180阅读 0赞

1.  单模式串匹配  
    BF 算法和 RK 算法  
    **BM 算法**和 KMP 算法
2.  多模式串匹配算法  
    Trie 树和 AC 自动机

### BM算法 ###

BM算法的核心思想是通过将模式串沿着主串大踏步的向后滑动，从而大大减少比较次数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时要尽量提高执行效率。这就需要模式串在向后滑动时，遵守坏字符规则与好后缀规则，同时采用一些技巧。

#### 坏字符规则 ####

从后往前逐位比较模式串与主串的字符，当找到不匹配的坏字符时，记录模式串的下标值si，并找到坏字符在模式串中，位于下标si前的最近位置xi（若无则记为-1），si-xi即为向后滑动距离。（但是坏字符规则向后滑动的步幅还不够大，于是需要好后缀规则。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 好后缀规则 ####

从后往前逐位比较模式串与主串的字符，当出现坏字符时停止。若存在已匹配成功的子串｛u｝，那么在模式串的｛u｝前面找到最近的｛u｝，记作｛u’｝。再将模式串后移，使得模式串的｛u’｝与主串的｛u｝重叠。若不存在｛u’｝，则直接把模式串移到主串的｛u｝后面。为了没有遗漏，需要找到最长的、能够跟模式串的前缀子串匹配的，好后缀的后缀子串（同时也是模式串的后缀子串）。然后把模式串向右移到其左边界，与这个好后缀的后缀子串在主串中的左边界对齐。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

### 何时使用坏字符规则和好后缀规则呢？ ###

首先在每次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两者中选择后移距离最大的方案执行。

技巧：  
1.通过散列表实现，坏字符在模式串中下标位置的快速查询。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

private static final int SIZE = 256; // 全局变量或成员变量
    private void generateBC(char[] b, int m, int[] bc) { 
      for (int i = 0; i < SIZE; ++i) { 
        bc[i] = -1; // 初始化bc
      }
      for (int i = 0; i < m; ++i) { 
        int ascii = (int)b[i]; // 计算b[i]的ASCII值
        bc[ascii] = i;
      }
    }
    
    
    public int bm(char[] a, int n, char[] b, int m) { 
      int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
      generateBC(b, m, bc); // 构建坏字符哈希表
      int i = 0; // i表示主串与模式串对齐的第一个字符
      while (i <= n - m) { 
        int j;
        for (j = m - 1; j >= 0; --j) {  // 模式串从后往前匹配
          if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
        }
        if (j < 0) { 
          return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
        // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
        i = i + (j - bc[(int)a[i+j]]); 
      }
      return -1;
    }

2.每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在模式串中与之匹配的另一个子串的位置。同时预计算模式串中（同长度的）后缀子串与前缀子串是否匹配并记录。在具体操作中直接使用，大大提高效率。  
3.如何快速记录模式串后缀子串匹配的另一个子串位置，以及模式串（相同长度）前缀与后缀子串石否匹配呢？先用一个suffix数组，下标值k为后缀子串的长度，从模式串下标为i（0~m-2）的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标值j赋给suffix\[k\]。若j为0，说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefix\[k\]设为true，否则设为false。k从0到m（模式串的长度）于是就得到了模式串所有前缀与后缀子串的匹配情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

// b表示模式串，m表示长度，suffix，prefix数组事先申请好了
    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) { 
      for (int i = 0; i < m; ++i) {  // 初始化
        suffix[i] = -1;
        prefix[i] = false;
      }
      for (int i = 0; i < m - 1; ++i) {  // b[0, i]
        int j = i;
        int k = 0; // 公共后缀子串长度
        while (j >= 0 && b[j] == b[m-1-k]) {  // 与b[0, m-1]求公共后缀子串
          --j;
          ++k;
          suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
        }
        if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
      }
    }

BM算法完整版

// a,b表示主串和模式串；n，m表示主串和模式串的长度。
    public int bm(char[] a, int n, char[] b, int m) { 
      int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
      generateBC(b, m, bc); // 构建坏字符哈希表
      int[] suffix = new int[m];
      boolean[] prefix = new boolean[m];
      generateGS(b, m, suffix, prefix);
      int i = 0; // j表示主串与模式串匹配的第一个字符
      while (i <= n - m) { 
        int j;
        for (j = m - 1; j >= 0; --j) {  // 模式串从后往前匹配
          if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
        }
        if (j < 0) { 
          return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
        }
        int x = j - bc[(int)a[i+j]];
        int y = 0;
        if (j < m-1) {  // 如果有好后缀的话
          y = moveByGS(j, m, suffix, prefix);
        }
        //好后缀和坏字符中最长的
        i = i + Math.max(x, y);
      }
      return -1;
    }
    
    // j表示坏字符对应的模式串中的字符下标; m表示模式串长度
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) { 
      int k = m - 1 - j; // 好后缀长度
      if (suffix[k] != -1) return j - suffix[k] +1;
      for (int r = j+2; r <= m-1; ++r) { 
        if (prefix[m-r] == true) { 
          return r;
        }
      }
      return m;
    }

### 应用 ###

grep命令 文本编辑器查找功能

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/4d53ab14c1ed48278a43682b64364dd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/b61494c4984541788cc806df27e2b62e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/3106d620670c42da9b3089b839ebb055.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/74749e3e49264a34a27fe008665797bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/493b570b18e14c65b968a8a2adf650b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/20248ca4a80d4f15a5e08310ba70d98e.png