BF算法

暴力匹配算法——朴素匹配算法

• 主串与模式串

  在主串中查找模式串

  ​ 比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。

  ​ 我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。

• 算法优劣

  • 缺点

    BF 算法的时间复杂度很高，是 O(n*m)

    但在实际的开发中，它却是一个比较常用的字符串匹配算法

  • 优点

    ​ 第一，实际的软件开发中，**大部分情况下，模式串和主串的长度都不会太长。**而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

    ​ 第二，**朴素字符串匹配算法思想简单，代码实现也非常简单。**简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。

• 所以，在实际的软件开发中，绝大部分情况下，朴素的字符串匹配算法就够用了

RK算法

BF算法的优化版，借助了哈希算法来优化比较

• 算法思想

  ​ 我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。

  ​ 如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

• 设计哈希算法1

  • 进制表示法

    ​ 我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。

    ​ 使用进制表示法，计算哈希值，不会产生哈希冲突，但是会出现值偏大，大到超出数的范围。

    

  • 哈希值计算规律

    ​ 相邻子串之间的哈希值的计算公式有一定的关系。

    

    • 计算技巧

      计算26^(m-1)的时候，可以提前计算好，存入数组中，以下标作为次方数，直接查。

      

  • 时间复杂度

    ​ 整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。

    ​ 第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。

    ​ 模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值。所以，这部分的时间复杂度也是 O(n)。

    ​ 所以，RK 算法整体的时间复杂度就是 O(n)。

• 设计哈希算法2

  哈希算法的设计方法有很多，我举一个例子说明一下。

  ​ 假设字符串中只包含 a～z 这 26 个英文字母，那我们每个字母对应一个数字，比如 a 对应 1，b 对应 2，以此类推，z 对应 26。我们可以把字符串中每个字母对应的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多了。

  • 应对哈希冲突

    ​ 之前我们只需要比较一下模式串和子串的哈希值，如果两个值相等，那这个子串就一定可以匹配模式串。但是，当存在哈希冲突的时候，有可能存在这样的情况，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。

    ​ **当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只需要再对比一下子串和模式串本身就好了。**当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。

• RK算法改进

  ​ 改进一：先计算模式串的hash值，记录下来，然后计算每一个子串的hash，计算一次，就对比一次，如果hash值匹配，在全量对比字符串。这样做可以不用关心hash冲突问题。不用事先计算出主串中所有子串的哈希值，计算一次，与模式串比较一次即可。

  ​ 改进二：计算子串hash值的时候只要计算到（n-m）处即可，剩下的子串长度小于模式串，不用计算.

BM算法

• 核心思想

  ​ BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。

  

• 原理分析

  BM算法的匹配顺序是==按照模式串下标从大到小的顺序，倒着匹配的==

  • 坏字符规则

    从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，我们把这个没有匹配的字符叫作坏字符（主串中的字符）。

    ​ 我们拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位(模式串的长度=2-(-1)=3)，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。

    

    • 移动次数

      1. 当发生不匹配的时候，我们把坏字符==对应==的模式串中的字符下标记作 si

      2. 如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作xi。如果不存在，我们把 xi 记作 -1。

      3. 那模式串往后移动的位数就等于 si-xi。

      4. 如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

         

    • 优缺点

      • 优点

        BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)

        匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。

      • 缺点

        根据 si-xi 计算出来的移动位数，有可能是==负数==

        比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。

        所以，BM 算法还需要用到“好后缀规则”。

  • 好后缀规则

    在从后往前匹配的时候，已经匹配到的字符串称为好后缀。

    

    • 滑动次数

      ​ 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

      简单来说，就是不要一下子移动一整个模式串的距离，看看模式串的开头部分和好后缀的结尾部分有没有重和的，有重和的就少移动几位。

      {u}为好后缀，{v}为能够匹配上的模式串的前缀子串

      滑动次数=模式串长度-{v}的长度

      

  • 方法选用

    ​ 我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

• 算法实现

  • 坏字符规则

    1. 可以预先将模式串中的每个字符及其下标都存储到散列表中。
    2. 计算下标xi的时候，可以直接查表获取，而不用遍历整个字符串。

    • 提供一种散列表的方法

      使用数组，将模式串单个字符的ascii码值作为数组下标，数组中的值为该字符在模式串中的下标。

    • 移动次数

    • bc为散列表数组，i为主串的循环大变量，j为模式串的循环小变量

      

  • 好后缀规则

    • 核心内容

      • 在模式串中，查找跟好后缀匹配的另一个子串；

      • 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

    • 实现方法1

      对模式串进行预处理,解决第一个核心内容

      ​ 因为好后缀子串也是模式串的后缀子串，所以我们可以提前将好后缀子串在模式串中再一次出现的起始下标值记录下来。

      将该值用suffix数组存储，下标为后缀子串的长度。

      1. 如果模式串中有多个（大于 1 个）子串跟后缀子串{u}匹配，存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。

      2. 如果该后缀没有再次出现，则将其设为-1

      比如说，后缀子串为b的时候，b再次出现在下标2处，且自身长度为1，所以suffix[1]=2

      后缀子串为cab的时候，cab再次出现在下标0处，且自身长度为3，所以suffix[3]=0

      后缀子串为bcab的时候，bcab没有再次出现，且自身长度为4，所以suffix[4]=-1

    

    • 实现方法2

      除了 suffix 数组之外，我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

      

      如果suffix数组的值为0，则说明该后缀自串也是模式串的前缀子串，prefix记为true；

    • 移动次数

      • 好后缀再次出现

        

      • 好后缀没有再次出现，但是有好后缀的后缀子串为模式串的前缀子串

        

      • 什么都没有

        

• ==优秀思想总结==

  代码实现具体细节不重要，重要的是处理问题的思想，及更好的优化思路

  • 使用散列表提高查找效率
  • 对于重复的，较难的计算，预处理好，需要的时候直接查(26^(m-1))
  • 善用之前的信息。

KMP算法

• 核心思想

  ​ KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？

  ​ 这里一次性移动了2位，2=主串虚线框中第一个a的下标-子串虚线框中第一个a的下标

  

• 最长可匹配前(后)缀

  把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

  

  最长子串的计算只有模式串有关，可以提前计算。用==next数组(前缀表)==表示。

  1. 数组的下标是每个前缀结尾字符下标
  2. 数组的值是这个前缀的 最长可以匹配前缀子串 的结尾字符下标。
     • 比如，aba可以匹配到的最长前缀子串为a，其下标为0
     • abab可以匹配到的最长前缀子串为ab，其下标为1
  3. ==前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。==
     • ==next[i]=x表示，s[0:i]具有长度为x+1的完全相同的前缀和后缀。==
     • 从next+1开始匹配,即前一个最长匹配前缀子串末尾的下一位。next中存的是末尾的下标，所有模式串从next+1开始匹配。
     • j = next[j - 1] + 1
     • 
  

• KMP算法代码

  // a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
  public static int kmp(char[] a, int n, char[] b, int m) {
      int[] next = getNexts(b, m);
      int j = 0;
      for (int i = 0; i < n; ++i) {
          while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
              j = next[j - 1] + 1;
          }
          //j为一次移动的次数，对于模式串来说，不用从0开始比了，一下子滑动到j处
          //进入循环的j为坏字符的下标
          //进入后更新j为最长匹配前缀的末尾字符串的下一位，即next[j-1]+1
          if (a[i] == b[j]) {
              ++j;
          }
          if (j == m) { // 找到匹配模式串的了
              return i - m + 1;
          }
      }
      return -1;
  }
  

• next数组计算方法

  • 思想

    在计算next[i]的时候，利用前面已经计算出的next[0],……next[i-1]。

    • 第一种情况（加字符相等）

      如在计算上文的next[3]和next[4]那样.以next[3]为例

      next[2]时,整个串为aba,最长前缀子串为a,这个a是下标为0的a，k=0,i=2,next[i]=k==>next[2]=0

      在计算next[3]时，整个串变为abab,新添加的这个b(下标为3)，刚好等于next[0]时的最长前缀子串的下一个字符b(下标为1)

      此时，next[3]的最长前缀子串为ab，所以next[1]=next[0]+1=1,k=1,i=3,next[i]=k==>next[3]=1

    • ==第二种情况(加字符不等)==

      设字符串为abxabcabxabx,共12位，下标从0到11

      ​ 在计算next[10]时，串为abxabcabxab,最长前缀子串为abxab,即k=4,i=10,next[10]=4

      ​ 在计算next[11]时，串为abxabcabxabx,新添加了一个x，而next[10]的最长前缀子串的下一个字符为c，二者不相等，即k=4,i=11,k'=k+1=5,next[5]!=next[11]，则找一个次长前缀子串，即为abxab的的最长前缀子串，即满足情况1的子串。简单来说，我下一个是x，你去找一个最长前缀子串，下一个也是x，符合情况1，这样可以直接用加法来解决。

      ​ k=next[4]=1,此时最长前缀子串为ab，str[k+1]=str[2]====x====str[i]=str[11],正好满足情况1，此时的最长前缀子串为abx，即next[11]=2。

  • 代码实现

    // b表示模式串，m表示模式串的长度
    private static int[] getNexts(char[] b, int m) {
        int[] next = new int[m];
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < m; ++i) {
            //去找满足情况1的子串
            while (k != -1 && b[k + 1] != b[i]) {
                k = next[k];//回溯
            }
            //找到了，++
            if (b[k + 1] == b[i]) {
                ++k;
            }
            //赋值
            next[i] = k;
        }
        return next;
    }
    

• 复杂度分析

  • 空间复杂度——next数组，O(n)
  • 时间复杂度
    • 求next数组——O(m)
      • 就是大循环的次数，小循序次数肯定小于m，设为k，即总体为O(k*m)
      • k相对于m来说，值很小，所以总的时间复杂度为O(m)
    • KMP算法——O(n)，同求next数组
    • ==总的——O(m+n)==

Trie树

Trie 树，也叫“字典树”。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

• 核心思想

  Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

  例如，我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。构造Trie树，则如下图所示。从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）——例如hi，hil,i和l两个结点都要标红，而i不是叶子结点。

  

• 查找

  • her

    分解为h,e,r最后找到红色结点，说明是一个完整的字符。

    

  • he

    分解为h,e最后没有找到红色结点，说明是一个完整的字符的字符前缀。

    

• Trie树实现

  假设字符串中只有26个小写字符，**则可以用一个大小为26的数组来存储子节点的指针。**不存在子节点的存null

  

  • 数据结构

    class TrieNode {
      char data;
      TrieNode children[26];
    }
    

  • 时间复杂度

    设总的字符串长度为n，要查找的字符串长度为k，则

    • 构建Trim树——O(n)
    • 构建好树，在树中查字符串——O(k)

• Trie树优化

  • Trie树 很耗内存

    上述说的，使用数组存子节点指针的方式，需要大量的存储空间，而且很多空间都是闲置的。

  • 改进

    • 可以将数组，改成散列表，跳表，红黑树等，稍微牺牲一些查询效率，以节约内存
    • 缩点优化——将斜树的内容放到一个结点，例如l,l,o可以存储在一起，llo，不影响查询

• Trie树与散列表、红黑树的比较

  • 查找定长的字符串

    在一组字符串中，查找一个固定的字符串，Trie树虽然效率很高，但是有很多缺点

    1. 第一，字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
    2. 第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
    3. 第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
    4. 第四，我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

    综上，查找固定长度的字符串，Trie树不如使用红黑树或者散列表。

  • 查找字符串前缀匹配的字符串

    Trie 树最有优势的是查找前缀匹配的字符串。对于这个功能，其他数据结构，爱莫能助

    • 实现搜索关键词提示功能
    • 实现代码(命令)自动补全功能

• 利用Trie树实现搜索关键词提示功能(最基本的功能实现)

  深入剖析搜索引擎

  

  假设，词库中有hello,her,hi,how,see,so

  • 输入h，展示hello,her,hi,how
  • 输入he，展示hello,her

AC自动机

BF 算法、RK 算法、BM 算法、KMP 算法,都是单模式串匹配算法， Trie 树，AC自动机都是多模式串匹配算法。

AC 自动机是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像单模式串中，KMP 算法与 BF 算法的关系一样。

• 利用Tire树实现多模式串匹配

  前面Trie那节介绍的是匹配一个固定长度的字符串问题，很短小，就一个主串匹配一个模式串

  • 多模式串匹配

    ​ 多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

  • 实现流程——借助上图的trie树

    ​ 设有超长字符串，作为主串（cheisesa），从第一个字符（c）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符h开始，重新在 Trie 树中匹配(重新从根节点开始搜索)。hei这个字符串可以匹配到，做相应处理。

    ​ 然后继续从s开始匹配,se符合，ses不符合。则继续从e开始匹配，重复此过程。

  • 缺点

    每次匹配失败后，从主串当前匹配字符往后移动一位，继续从根节点开始重新匹配，就相当于BF算法在匹配时做法。

    举例：假设匹配abcd

    • Trie树

      1. abc没问题,继续匹配，d和e匹配不上

      2. 匹配起始结点从a后移一维，重新开始匹配bcd，匹配完成。

      3. 分析：b,c进行了重复匹配.在模式串abcd中已经匹配过了bc，在模式串bcd中再次进行了b和c的匹配。

    • AC自动机

      1. abc没问题,继续匹配，d和e匹配不上
      2. 通过c的失败指针指向模式串bcd的c，这个d刚好可以和abcd中d匹配上，如果到了结尾，可以直接输出匹配到了bcd
      3. 分析:在模式串abcd中已经匹配过了bc，在模式串bcd中只匹配了d

    

• AC自动机核心思想

  AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

  • 数据结构

    public class AcNode {
        public char data; 
        public AcNode[] children = new AcNode[26]; // 字符集只包含a~z这26个字符
        public boolean isEndingChar = false; // 结尾字符为true
        public int length = -1; // 当isEndingChar=true时，记录模式串长度
        public AcNode fail; // 失败指针
        public AcNode(char data) {
            this.data = data;
        }
    }
    

  • AC自动机的构建

    • 将多个模式串构建成 Trie 树；构建一个敏感词的Trie树。——详见Trie树
    • 在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

• 构建失败指针

  核心思想就跟构造KMP的next数组一样

  • 初始构建失败指针

    ​ 假设，我们要匹配的主串为abcd，模式串分别是 c，bc，bcd，abcd；

    ​ 我们沿 Trie 树走到 p 节点，也就是下图中的紫色节点，那 p 的失败指针就是从 root 走到紫色节点形成的字符串 abc的末尾c，指向跟所有模式串前缀匹配的最长可匹配后缀子串，就是箭头指的 bc 模式串的c。

    

    ​ 如果我们把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上层。

    • 可匹配后缀子串

      ​ 字符串 abc 的后缀子串有两个 bc，c，我们拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，那我们就把这个后缀子串叫作可匹配后缀子串。

  • 构建子节点失败指针

    我们假设节点 p 的失败指针指向节点 q，我们看节点 p 的子节点 pc 对应的字符，是否也可以在节点 q 的子节点中找到。

    • 同加相等====第一种情况

      ​ 如果找到了节点 q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc。

      

    • 同加不等====第二种情况

      ​ 如果节点 q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指针，这里有没有很像 KMP 算法里求 next 的过程？k=next[k]），继续上面的查找，直到 q 是 root 为止，如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root。

      

  • 完整的AC自动机构建

    

• 如何在AC自动机上匹配主串

  public void match(char[] text) { // text是主串
      int n = text.length;
      AcNode p = root;
      for (int i = 0; i < n; ++i) {
          int idx = text[i] - 'a';
          //前面的条件是，在匹配模式串时，当前模式串的没有text[i]这个字符，即数组部分存储null指针。
          //一直找到有text[i]这个字符的模式串，由于是通过失败指针跳跃的，
          //所以该模式串前面虽然没有匹配过,但是重新匹配的话肯定能匹配上，换而言之就是，它的前面的字符串肯定在主串中出现过，且在其他模式串中匹配过。
          while (p.children[idx] == null && p != root) {
              p = p.fail; // 失败指针发挥作用的地方
          }
          //找到了有text[i]这个字符模式串
          p = p.children[idx];
          if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
          
          AcNode tmp = p;
          while (tmp != root) { // 打印出可以匹配的模式串
              if (tmp.isEndingChar == true) {
                  int pos = i-tmp.length+1;
                  System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
              }
              tmp = tmp.fail;
          }
      }
  }
  

• 性能分析——不准

  设总的字符串(所有模式串的长度总和)长度为n，要查找的字符串(主串)长度为k，则

  • 构建AC自动机
    • 构建Trie树——O(n)
    • 构建失败指针——O(n)
  • 匹配主串——O(k)