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

AC自动机-hdu2222

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

这篇博客我以hdu2222这道模版题为例详细的讲解一下AC自动机。

AC自动机

简介
AC自动机(Aho-Corasick automation),该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。
一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。
要学AC自动机最好先有KMP和字典树Trie的基础,AC自动机实际上就像是在Trie上进行KMP的算法。

字典树Trie:http://blog.csdn.net/williamsun0122/article/details/71056547

KMP:http://blog.csdn.net/WilliamSun0122/article/details/75576868

思想

我们以5个单词say,she,shr,he,her和字符串yasherhs为例,问多少个单词在字符串中出现过。

运用AC自动机的时候先构造Trie树再运用KMP的思想即可。这里的Trie树有所不同,具体构造如下:

struct node{
    node *next[maxn];
    node *fail;
    int num;
    node()
    {
        for(int i=0;i<26;i++) next[i] = NULL;
        fail = NULL;
        num = 0;
    }
};

可以看出多了fail指针。
这里的fail指针就类似KMP里面的next数组,是匹配失败后的指向。
先把单词插入到Trie树中:

void ac_insert()
{
    node *p = root;
    for(int i=0;word[i];i++)
    {
        int id = word[i]-'a';
        if(p->next[id]==NULL) p->next[id] = new node;
        p = p->next[id];
    }
    p->num++;
}

构造Trie树如图
AC自动机-hdu2222

然后我们详细讲解一下AC自动机最重要的部分,就是fail失败指针的求解。我们对着图看我的讲解。
AC自动机-hdu2222

我们是用BFS来构造fail指针,并且运用的是KMP的思想。
最开始先让root入队。队列{root}
第1次循环时处理与root相连的字符即h和s。因为第一个字符不匹配需要重新匹配,所以h和s的fail指针都指向root(root是Trie入口,没有实际含义)即图中(1)和(2)。此时队列{h,s}
第二次循环时处理与h相连的字符即e。当当前字符e失配时应该将其fail指针指向当前字符串(he)的最长后缀和Trie树中前缀的匹配(就是相当于指向其父节点h的fail指针指向的节点,看其有没有当前节点e的匹配,有的话就指向它,没有的话可以一直向上找直到fail指针指向root)。这里h的fail指针指向root,而root没有e的匹配,所以把e的fail指针指向root。此时队列{s,e}
第三次循环时处理与s相连的字符a和h。其中a与第二次循环的e情况相同,将其fail指针指向root。h其父节点s的fail指针指向root,而root有h的匹配,所以把h的fail指针指向与root相连的h节点。
之后情况依此类推。
代码如下:

void ac_setFail()
{
    node *p,*tmp;
    queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        p = q.front(),q.pop();
        for(int i=0;i<26;i++)
        {
            if(p->next[i]==NULL) continue;
            if(p==root)
            {
                p->next[i]->fail = root;
                q.push(p->next[i]);
            }
            else
            {
                tmp = p->fail;
                while(tmp)
                {
                    if(tmp->next[i])
                    {
                        p->next[i]->fail = tmp->next[i];
                        break;
                    }
                    tmp = tmp->fail;
                }
                if(tmp==NULL) p->next[i]->fail = root;
                q.push(p->next[i]);
            }
        }
    }
}

最后就是AC自动机的多模匹配。匹配过程也与KMP的类似,并不是很难,我直接贴代码,代码里面有一些注释。

int ac_automation()
{
    int ans=0;
    node *p = root;
    node *tmp;
    for(int i=0;str[i];i++)
    {
        int id = str[i]-'a';
        //当当前节点不是root且没有该字符(id)的匹配就一直想上找
        while(p->next[id]==NULL && p!=root) p = p->fail;
        //找到有id的匹配不然就是root
        if(p->next[id]!=NULL) p = p->next[id];
        tmp = p;
        //找到该匹配后要循环向上计数,不然可能会有遗漏。
        //比如she和he不循环向上找的话就只会加she一个
        while(tmp!=root)
        {
            if(tmp->num>0)
            {
                ans += tmp->num;
                //计数后将其置0,避免重复计数
                tmp->num = 0;
            }
            else tmp = tmp->fail;
        }
    }
    return ans;
}

以上就是我对AC自动机的理解,希望对大家有帮助。

参考博客:http://blog.csdn.net/niushuai666/article/details/7002823

hdu2222

这题就是个模版题,看懂上面的内容之后就可以直接A了。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;

int t,n;

char word[55],str[maxn];

struct node{
    node *next[26];
    node *fail;
    int num;
    node()
    {
        for(int i=0;i<26;i++) next[i] = NULL;
        fail = NULL;
        num = 0;
    }
};

node *root;

void init()
{
    root = new node;
}

void ac_insert()
{
    node *p = root;
    for(int i=0;word[i];i++)
    {
        int id = word[i]-'a';
        if(p->next[id]==NULL) p->next[id] = new node;
        p = p->next[id];
    }
    p->num++;
}

void ac_setFail()
{
    node *p,*tmp;
    queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        p = q.front(),q.pop();
        for(int i=0;i<26;i++)
        {
            if(p->next[i]==NULL) continue;
            if(p==root)
            {
                p->next[i]->fail = root;
                q.push(p->next[i]);
            }
            else
            {
                tmp = p->fail;
                while(tmp)
                {
                    if(tmp->next[i])
                    {
                        p->next[i]->fail = tmp->next[i];
                        break;
                    }
                    tmp = tmp->fail;
                }
                if(tmp==NULL) p->next[i]->fail = root;
                q.push(p->next[i]);
            }
        }
    }
}

int ac_automation()
{
    int ans=0;
    node *p = root;
    node *tmp;
    for(int i=0;str[i];i++)
    {
        int id = str[i]-'a';
        while(p->next[id]==NULL && p!=root) p = p->fail;
        if(p->next[id]!=NULL) p = p->next[id];
        tmp = p;
        while(tmp!=root)
        {
            if(tmp->num>0)
            {
                ans += tmp->num;
                tmp->num = 0;
            }
            else tmp = tmp->fail;
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",word);
            ac_insert();
        }
        ac_setFail();
        scanf("%s",str);
        printf("%d\n",ac_automation());
    }
    return 0;
}