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

2018-10-25  本文已影响0人  jenye_

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


主要内容:


什么是AC自动机

Aho-Corasick automaton,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。要学会AC自动机,我们必须知道什么是Trie,也就是字典树。Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
(来源:百度百科)

用来做什么?

AC自动机针对是多模式串匹配问题。例:给几个关键词(模式串),再给一篇文章,判断关键词是否在文章中出现,或出现的次数。

前置知识

算法分析

1. 构建Trie树

正常的构建过程,每插入一个模式串对每个字符进行遍历,如果节点不存在就创建,继续向下层拓展。(结尾的节点需要特殊标志)
假设模式串有:she , he ,say, her, shr
我们要构建一棵字典树:


2.设置失败节点

设置失败节点是AC自动机的关键所在,在KMP算法中失败数组,指向的是失配之后继续匹配的位置,最终的效果就是对目标串扫描一遍,不需要回溯。而KMP中找的是最长公共前后缀。AC自动机找的是父节点的失败节点的子节点。
我们定义

struct {
      Node* father  //父节点
      Node* fail  //失败节点
      Node* children[26]  //孩子节点
}Node
注:该代码为了理解,与实际节点有所不同

我们通过bfs遍历节点,每个节点处理完毕后,孩子入队,直到队列为空。
一般情况:
假设当前节点为p,那么我们需要找到p->father ->fail ->child,查看child是否有与p节点字母相同的节点,若有 p->fail = p->father->fail->children[与p相同],若无我们要寻找p->father->fail->fail,直到找到与p对应的child节点或达到root节点。
第一层节点:
p->fail = root;
(实际的代码编写中,并不需要设置父节点的指针,可以认为p是父节点,对他的children节点进行遍历设置,操作将会是p->children[i]->fail = p->fail->children)
失败节点的正确性:失败节点的特点是与原节点的字母相同,那么我们找到父节点的失败节点,找到的节点与原节点的父节点相同。那么父节点的失败节点(p_father->fail)找的是父节点的父节点(p_father->father),这样以此类推,查找的路径都将是正确的。

对目标串进行匹配

从root节点开始

代码实现

经典AC自动机

代码来自源AC自动机算法详解 (转载)

const int kind = 26; 
struct node
{
    node *fail;       //失败指针
    node *next[kind]; //Tire每个节点的个子节点(最多个字母)
    int count;        //是否为该单词的最后一个节点
    node()            //构造函数初始化
    {
        fail=NULL;
        count=0;
        memset(next,NULL,sizeof(next));
    }
}*q[500001];          //队列,方便用于bfs构造失败指针
char keyword[51];     //输入的单词
char str[1000001];    //模式串
int head,tail;        //队列的头尾指针
void insert(char *str,node *root){ 
    node *p=root;
    int i=0,index;
    while(str[i])
    {
        index=str[i]-'a';
        if(p->next[index]==NULL) p->next[index]=new node();
        p=p->next[index];
        i++;
    }
    p->count++;     //在单词的最后一个节点count+1,代表一个单词
}
 void build_ac_automation(node *root){
    int i;
    root->fail=NULL;
    q[head++]=root;
    while(head!=tail)
    {
        node *temp=q[tail++];
        node *p=NULL;
        for(i=0; i<26; i++)
        {
            if(temp->next[i]!=NULL)
            {
                if(temp==root) temp->next[i]->fail=root;
                else
                {
                    p=temp->fail;
                    while(p!=NULL)
                    {
                        if(p->next[i]!=NULL)
                        {
                            temp->next[i]->fail=p->next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL) temp->next[i]->fail=root;
                }
                q[head++]=temp->next[i];
            }
        }
    }
}
int query(node *root){ 
    int i=0,cnt=0,index,len=strlen(str);
    node *p=root;
    while(str[i])
    {
        index=str[i]-'a';
        while(p->next[index]==NULL && p!=root) p=p->fail;
        p=p->next[index];
        p=(p==NULL)?root:p;
        node *temp=p;
        while(temp!=root && temp->count!=-1)
        {
            cnt+=temp->count;
            temp->count=-1;
            temp=temp->fail;
        }
        i++;
    }
    return cnt;
}
上一篇 下一篇

猜你喜欢

热点阅读