随笔：152 文章：0 评论：129 引用：0

HDU 2222 AC自动机

http://www.cppblog.com/mythit/archive/2009/07/30/80633.html
http://www.cnblogs.com/destinydesigner/archive/2009/10/15/1584191.html
推荐以上两个链接作为了解AC自动机的材料，加上2006年的一篇Trie图的论文。
模板+代码如下：

HDU 2222
#include<iostream>
#include<queue>
using namespace std;
struct Trie
{
    Trie *next[26];
    Trie *fail;
    int cnt;
    Trie()
    {
        cnt=0;
        memset(next,NULL,sizeof(next));
        fail=NULL;
    }
} *root;
void build()
{
    root=NULL;
    root=new Trie; 
}
void insert(char *s)
{
    Trie *r=root,*p;
    int i=0;
    while(s[i])
    {
        if(r->next[s[i]-'a']==NULL)
        {
            p=new Trie();
            r->next[s[i]-'a']=p;
        }
        r=r->next[s[i]-'a'];
        i++;
    }
    r->cnt++;
} 
void BuildTrie()
{
    int i;
    Trie *r=root,*p,*tmp;
    root->fail=NULL;
    queue<Trie *>q;
    q.push(root);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(i=0;i<26;i++)
            if(p->next[i]!=NULL)
            {
                if(p==root)
                    p->next[i]->fail=root;
                else
                {
                    tmp=p->fail;
                    while(tmp!=root&&tmp->next[i]==NULL)
                        tmp=tmp->fail;
                    if(tmp->next[i]==NULL)
                        p->next[i]->fail=root;
                    else p->next[i]->fail=tmp->next[i];
                }
                q.push(p->next[i]);
            }
    }
}
int check(char *s)
{
    int c=0;
    Trie *r=root,*p,*tmp;
    while(*s)
    {
        int idx=*s-'a';
        while(r->next[idx]==NULL&&r!=root)
            r=r->fail;
        r=r->next[idx];
        if(r==NULL)
            r=root;
        tmp=r;
        while(tmp!=root)
        {
            c+=tmp->cnt;
            tmp->cnt=0;
            tmp=tmp->fail;
        }
        s++;
    }
    return c;
}
int cas,n;
char txt[1000010],ss[52];
int main()
{
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        build();
        while(n--)
        {
            scanf("%s",ss);
            insert(ss);
        }
        scanf("%s",txt);
        BuildTrie();
        printf("%d\n",check(txt));
    }
    return 0;
}

发表于 2010-01-12 13:34 Headacher 阅读(686) 评论(0) 编辑收藏引用所属分类: 数据结构和算法

只有注册用户登录后才能发表评论。


相关文章: POJ 2043 扫描计算几何 POJ 1113 凸包 POJ 3164 最小树形图朱刘算法 POJ 2761 SBT 静态数组实现 POJ 2778 自动机_矩阵乘法 HDU 2222 AC自动机数位统计无耻IO优化哦哦有上下界的可行流

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

CALENDER

2008年10月

日

一

二

三

四

五

六

公告

留言簿(8)

随笔分类

随笔档案

ACM Teammates

The One

May (rss)

搜索

积分与排名

积分 - 129223
排名 - 194