AC自动机

作者: TomGui | 来源:发表于2020-07-05 11:43 被阅读0次

字符串匹配算法

单模式串匹配算法

是在一个模式串和一个主串之间进行匹配,也就是说,在一个主串中查找一个模式串。

多模式串匹配算法

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

经典的多模式串匹配算法:AC自动机

AC自动机算法,全称是Aho-Corasick算法。其实,Trie树跟AC自动机之间的关系,就像单串匹配中朴素的串匹配算法,跟KMP算法之间的关系一样,只不过前者针对的是多模式串而已。所以,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树上构建失败指针(相当于KMP中的失效函数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;
  }
}

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);
    }
  }
}

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自动机算法AC自动机算法详解hdu 2222 ac自动机入门...

  • 自动AC机?不,是AC自动机

    今天我们来介绍一点进阶的知识——AC自动机。 AC自动机是啥 AC自动机是什么呢?是不是用了这个算法,不管什么题目...

  • 【AC自动机】AC自动机可以帮你自动AC吗

    参考博文:AC自动机算法详解 (转载) (原文作者:DarkRaven,原文的链接失效了)图片来源:AC自动机算...

  • AC自动机-去除敏感字符

    AC自动机 AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名...

  • lucene中文分词

    IK中文分词 DoubleArrayTrie的AC自动机

  • 字符串算法小结

    hash kmp和ac自动机 后缀数组,后缀自动机,后缀树 扩展kmp manacher算法 回文自动机 可删改的...

  • AC 自动机

    AC自动机 AC自动机是一个经典的多模式串匹配算法,它可以实现对主串的一次扫描来匹配多个模式串的功能。实现AC自动...

  • 回文树(附模板题URAL-1960)

    (最好事先学习过kmp,Trie,AC自动机)回文树,有效解决各类回文问题的超级666的树形结构 集AC自动机的f...

  • AC自动机_模板

    AC自动机: 求多个字符串是否在主串中出现过。可依据情况分别求出出现次数,出现位置等。 AC自动机入门Keywor...

  • AC自动机

    参考资料:AC自动机GIF动图(来自油管) 以下文章节选自:王争老师 AC自动机:如何用多模式串匹配实现敏感词过滤...

网友评论

    本文标题:AC自动机

    本文链接:https://www.haomeiwen.com/subject/mufvqktx.html