欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

强势 图解 AC自动机(保证您一次就能学会!)

程序员文章站 2022-06-04 12:30:42
...

前置技能

简介

看dalao们AC自动机的Blog,大多数奆奆都会感性地说: AC_automation = KMP+TRIE<!--more--> 然而在作者重蹈覆辙辗转反侧n次后才明白,这东西说了等于没说。

  • AC自动机是一种有限状态自动机(说了等于没说),它常被用于多模式串的字符串匹配。
  • 在学完AC自动机,笔者也总结出一句说了等于没说的话: AC自动机是以TRIE的结构为基础,结合KMP的思想建立的。

建立AC自动机

建立一个AC自动机通常需要两个步骤:

  • 基础的TRIE结构:将所有的模式串构成一棵Trie。
  • KMP的思想:对Trie树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。

TRIE构建

  • 和trie的insert操作一模一样(强调!一模一样!)
  • 因为我们只利用TRIE的结构,所以只需将模式串存入即可。

构造失配( failfailfail )指针

在讲构造以前,先来对比一下这里的 failfailfail 指针与KMP中的next指针:

  • 共同点-两者同样是在失配的时候用于跳转的指针。
  • 不同点-KMP要求的是最长相同真前后缀,而AC自动机只需要相同后缀即可。
    • 因为KMP只对一个模式串做匹配,而AC自动机要对多个模式串做匹配。
    • 有可能 failfailfail 指针指向的结点对应着另一个模式串,两者前缀不同。
    • 也就是说,AC自动机在对匹配串做逐位匹配时,同一位上可能匹配多个模式串。
    • 因此 failfailfail 指针会在字典树上的结点来回穿梭,而不像KMP在线性结构上跳转。

下面介绍构建 failfailfail 指针的基础思想:(强调!基础思想!基础!)

  • 构建 failfailfail 指针,可以参考KMP中构造next数组的思想
  • 我们利用部分已经求出 failfailfail 指针的结点推导出当前结点的 failfailfail 指针。具体我们用BFS实现:
    • 考虑字典树中当前的节点u,u的父节点是p,p通过字符c的边指向u。
    • 假设深度小于u的所有节点的 failfailfail 指针都已求得。那么p的 failfailfail 指针显然也已求得。
    • 我们跳转到p的 failfailfail 指针指向的结点 fail[p]fail[p]fail[p]
      • 如果结点 fail[p]fail[p]fail[p] 通过字母 ccc 连接到的子结点 www 存在:
        • 则让u的fail指针指向这个结点 wwwfail[u]=wfail[u]=wfail[u]=w )。
        • 相当于在 pppfail[p]fail[p]fail[p] 后面加一个字符 ccc ,就构成了 fail[u]fail[u]fail[u]
      • 如果 fail[p]fail[p]fail[p] 通过字母 ccc 连接到的子结点 www 不存在:
        • 那么我们继续找到 fail[fail[p]]fail[fail[p]]fail[fail[p]] 指针指向的结点,重复上述判断过程,一直跳 failfailfail 指针直到根节点。
        • 如果真的没有,就令 fail[u]=fail[u]=fail[u]= 根节点。
  • 如此即完成了 failfailfail 指针的构建。

下面放一张GIF帮助大家理解: 对字典树{i,he,his,she,hers}构建 failfailfail 指针:

  • 黄色结点表示当前的结点u,绿色结点表示已经BFS遍历完毕的结点,红/橙色的边表示 failfailfail 指针。

  • 2号节点的 failfailfail 指针画错了, fail[2]=0fail[2]=0fail[2]=0 . 强势 图解 AC自动机(保证您一次就能学会!)

  • 我们重点分析结点6的 failfailfail 指针构建: 强势 图解 AC自动机(保证您一次就能学会!)

  • 找到6的父节点5,5的 failfailfail 指针指向10,然而10结点没有字母's'连出的边;

  • 所以跳到10的 failfailfail 指针指向的结点0,发现0结点有字母's'连出的边,指向7结点;

  • 所以 fail[6]=7fail[6]=7fail[6]=7 .

另外,在构建 failfailfail 指针的同时,我们也对TRIE中模式串的结尾构建 failfailfail 指针。这样在匹配到结尾后能自动跳转到下一个匹配项。具体见代码实现。

从代码深入剖析

框架

const int N=1000;
struct AC_automaton{
    int tr[N][26],cnt;//TRIE
    int e[N];//标记这个结点是不是字符串结尾
    int fail[N];//fail指针
void insert(char * s){}//插入模式串
void build(){}//构建fail指针
int query(char *t){}//匹配函数

};
AC_automation ac;
}

字典树与字典图

  • 关于insert()笔者不做分析,先来看build():
    void build(){
    queue<int>q;
    memset(fail,0,sizeof(fail));
    for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);//Q1
    while(!q.empty()){
        int k=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(tr[k][i]){
                fail[tr[k][i]]=tr[fail[k]][i];//Q2
                q.push(tr[k][i]);
            }
            else tr[k][i]=tr[fail[k]][i];//Q3
        }
    }
    }

    首先声明了一个队列用于BFS,并清空 failfailfail 数组。

这里的字典树根节点为0,我们将根节点的子节点一一入队。

  • Q1-等等,为什么不将根节点入队,非要将它的子节点入队?

然后开始BFS:

  • 每次取出队首的结点k。注意,结点k本身的 failfailfail 指针已经求得,我们要求的是k的子节点们的 failfailfail 指针。
  • 然后遍历字符集(这里是0-25,对应a-z):
    • 如果字符i对应的子节点存在,我们就将这个子节点的 fail​fail​fail 指针赋值为 fail[k]fail[k]fail[k] 的字符i对应的结点。
    • Q2-不是应该用while循环,不停的跳 failfailfail 指针,判断是否存在字符i对应的结点,然后赋值吗?怎么一句话就完了?
    • 否则,k结点没有字符i对应的子节点,就将 fail[k]fail[k]fail[k] 的字符i对应的子节点编号赋值给k
    • Q3-等等,说好的字典树呢?怎么将 fail[k]fail[k]fail[k] 的子节点直接赋成k的子节点去了?

这三个Questions构成了 failfailfail 指针构建的精髓。

Q1

  • 若将根节点入队,则在第一次BFS的时候,会将根节点的子节点的 failfailfail 指针标记为本身。
  • 而将根节点的子节点入队,也不影响算法正确性(因为 failfailfail 指针初始化为0)

Q2&Q3

  • Q2与Q3的代码是相辅相成的。

  • 简单地来讲,我们将 failfailfail 指针跳转的路径做了压缩(就像并查集的路径压缩),使得本来需要跳很多次 failfailfail 指针变成跳一次。

  • 而这个路径压缩的就是Q3的代码在做的事情之一

  • 我们将之前的GIF图改一下: 强势 图解 AC自动机(保证您一次就能学会!)

  • 蓝色结点表示BFS遍历到的结点k,深蓝色、黑色的边表示执行完Q3代码连出的字典树的边。

  • 可以发现,众多交错的黑色边将字典树变成了字典图。

  • 图中省略了连向根节点的黑边(否则会更乱)。

  • 我们重点分析一下结点5遍历时的情况: 强势 图解 AC自动机(保证您一次就能学会!)

  • 显然,本来应该跳2次才能找到7号结点,但是我们通过10号结点的黑色边直接通过字母s找到了7号结点。

  • 因此,Q2结合了Q3的代码,就能在 O(1)O(1)O(1) 的时间内对单个结点构造 failfailfail 指针。

这就是build完成的两件事:构建 failfailfail 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。

多模式匹配

  • 接下来分析匹配函数query():
    int query(char *t){
    int p=0,res=0;
    for(int i=0;t[i];i++){
        p=tr[p][t[i]-'a'];//Q
        for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1;
    }
    return res;
    }
  • 声明p作为字典树上当前匹配到的结点,res即返回的答案
  • 循环遍历匹配串,p在字典树上跟踪当前字符。
  • 利用 failfailfail 指针找出所有匹配的模式串,累加到答案中。然后清0。
  • e[j]e[j]e[j] 取反的操作用来判断 e[j]e[j]e[j] 是否等于-1。
  • Q-读者可能纳闷了:你这里的p一直在往字典树后面走,没有跳 failfailfail 指针啊!这和KMP的思想不一样啊,怎么匹配得出来啊

Answer to Q

  • 还记得刚才的字典图吗?事实上你并不是一直在往后跳,而是在图上穿梭跳动。比如,刚才的字典图: 强势 图解 AC自动机(保证您一次就能学会!)

  • 我们从根节点开始尝试匹配ushersheishis,那么p的变化将是: 强势 图解 AC自动机(保证您一次就能学会!)

  • 红色结点表示p结点,粉色箭头表示p在字典图上的跳转,浅蓝色的边表示成功匹配的模式串,深蓝色的结点表示跳 failfailfail 指针时的结点。

  • 其中的部分跳转,我们利用的就是新构建的字典图上的边,它也满足后缀相同(sher和her),所以自动跳转到下一个位置。

  • 综上, failfailfail 指针的意义是,在匹配串同一个位置失配时的跳转指针,这样就利用 failfailfail 指针在同一位置上进行多模式匹配,匹配完了,就在字典图上自动跳转到下一位置。

总结

到此,你已经理解了整个AC自动机的内容。我们一句话总结AC自动机的运行原理: 构建字典图实现自动跳转,构建失配指针实现多模式匹配。

代码

const int N=1000;
struct AC_automaton{
    int tr[N][26],cnt;//TRIE
    int e[N];//标记字符串结尾
    int fail[N];//fail指针
void insert(char * s){//插入模式串
    int p=0;
    for(int i=0;s[i];i++){
        int k=s[i]-'a';
        if(!tr[p][k])tr[p][k]=++cnt;
        p=tr[p][k];
    }
    e[p]++;
}
void build(){
    queue&lt;int&gt;q;
    memset(fail,0,sizeof(fail));
    for(int i=0;i&lt;26;i++)if(tr[0][i])q.push(tr[0][i]);
        //首字符入队
        //不直接将0入队是为了避免指向自己
    while(!q.empty()){
        int k=q.front();q.pop();//当前结点
        for(int i=0;i&lt;26;i++){
            if(tr[k][i]){
                fail[tr[k][i]]=tr[fail[k]][i];//构建当前的fail指针
                q.push(tr[k][i]);//入队
            }
            else tr[k][i]=tr[fail[k]][i];
                //匹配到空字符,则索引到父节点fail指针对应的字符,以供后续指针的构建
                //类似并差集的路径压缩,把不存在的tr[k][i]全部指向tr[fail[k]][i]
                //这句话在后面匹配主串的时候也能帮助跳转
        }
    }
}
int query(char *t){
    int p=0,res=0;
    for(int i=0;t[i];i++){
        p=tr[p][t[i]-'a'];
        for(int j=p;j&amp;&amp;~e[j];j=fail[j])res+=e[j],e[j]=-1;
    }
    return res;
}


%%%Sshwy,tql\%\%\%Sshwy,tql

相关标签: # AC自动机