【数据结构与算法】字符串匹配 AC自动机

￡神魔★判官ぃ 2022-12-01 01:28 117阅读 0赞

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

### AC 自动机 ###

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

![在这里插入图片描述][20200825161104354.png_pic_center]

### AC 自动机的构建 ###

*  将多个模式串构建成 Trie 树；
 *  \-在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

public void buildFailurePointer() { 
      Queue<AcNode> queue = new LinkedList<>();
      root.fail = null;
      queue.add(root);
      while (!queue.isEmpty()) { 
        AcNode p = queue.remove();
        for (int i = 0; i < 26; ++i) { 
          AcNode pc = p.children[i];
          if (pc == null) continue;
          if (p == root) { 
            pc.fail = root;
          } else { 
            AcNode q = p.fail;
            while (q != null) { 
              AcNode qc = q.children[pc.data - 'a'];
              if (qc != null) { 
                pc.fail = qc;
                break;
              }
              q = q.fail;
            }
            if (q == null) { 
              pc.fail = root;
            }
          }
          queue.add(pc);
        }
      }
    }

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

### AC 自动机的匹配 ###

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

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';
        while (p.children[idx] == null && p != root) { 
          p = p.fail; // 失败指针发挥作用的地方
        }
        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;
        }
      }
    }

### 时间复杂度 ###

AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在 AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。  
**将多个模式串构建成 AC 自动机**  
Trie 树构建的时间复杂度是 O(m*len)，其中 len 表示敏感词的平均长度，m 表示敏感词的个数。  
每个节点构建失败指针的时间复杂度是 O(len)。整个失败指针的构建过程就是 O(k*len)。  
**AC 自动机做匹配**  
for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 O(len)，所以总的匹配的时间复杂度就是 O(n\*len)。  
实际情况下，可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。

[20200825161104354.png_pic_center]: /images/20221123/46781c04b5ad427f9af3564ef009dd70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/06cd7c66c07a49669a30fa4eb506640b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/81de23084ddf4d64940b76fbdbeaeeb1.png