AC自动机

时间：2011-05-13 来源：奋斗青春

去年就见到过这个词，不过一直没有去看，不是很理解其中的算法，可能是对kmp还没能够了解透彻。。

一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。

要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。

AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。

详见：http://www.cppblog.com/mythit/archive/2009/04/21/80633.html （AC自动机算法详解)

贴个模板吧：

hdu 2222 经典ac自动机

# include<stdio.h>
# include<queue>
# include<string.h>
# define MAX 26
using namespace std;
struct Trie{
        int count;
        struct Trie *next[MAX],*fail;
};
queue<Trie *>q;
char keyword[55];//记录单词
char str[1000005];//记录模式串 
Trie *NewTrie()
{
        int i;
        Trie *temp=new Trie;
        temp->count=0;
        for(i=0;i<MAX;i++)
                temp->next[i]=NULL;
        return temp;
}
void Insert(Trie *p,char s[])
{
        int i;
        Trie *temp=p;
        i=0;
        while(s[i])
        {
                if(temp->next[s[i]-'a']==NULL) temp->next[s[i]-'a']=NewTrie();
                temp=temp->next[s[i]-'a'];
                i++;
        }
        temp->count++;
}
void bulid_ac_automation(Trie *root)
{
        int i;
        q.push(root);
        root->fail=NULL;
        while(!q.empty())
        {
                Trie *temp=q.front();
                q.pop();
                Trie *p=NULL;
                for(i=0;i<MAX;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;
                                                }//if
                                                p=p->fail;
                                        }//while
                                        if(p==NULL) temp->next[i]->fail=root;
                                }//else
                                q.push(temp->next[i]);
                        }//if
                }//for
        }//while
}//void
int query(Trie *root)
{
        int i,cnt,index,len;
        i=0;
        cnt=0;
        len=strlen(str);
        Trie *p=root;
        while(str[i])
        {
                index=str[i]-'a';
                while(p->next[index]==NULL && p!=root) p=p->fail;
                p=p->next[index];
                if(p==NULL) p=root;
                Trie *temp=p;
                while(temp!=root && temp->count!=-1)
                {
                        cnt+=temp->count;
                        temp->count=-1;
                        temp=temp->fail;
                }
                i++;
        }
        return cnt;
}
int main()
{
        int i,n,ncase,cnt;
        Trie *p;
        scanf("%d",&ncase);
        while(ncase--)
        {
                p=NewTrie();
                scanf("%d",&n);
                for(i=1;i<=n;i++)
                {
                        scanf("%s",keyword);
                        Insert(p,keyword);
                }
                scanf("%s",str);
                bulid_ac_automation(p);
                cnt=query(p);
                printf("%d\n",cnt);
        }
        return 0;
}