AC自动机-hdu2222

这篇博客我以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自动机最重要的部分，就是fail失败指针的求解。我们对着图看我的讲解。

我们是用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;
}