关闭

Duan2baka的AC自动机模板!

171人阅读 评论(0) 收藏 举报

HDU[2222] Keywords Search

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2222

AC自动机常用于多模字符串匹配问题

代码如下:

#include<cstring>
#include<ctype.h>
#include<cstdio>
#include<queue>
#define N 1000050
using namespace std;
inline int read(){
    int x;
    scanf("%d",&x);
    return x;
}
int T,n;
char c[N];
struct Node{
    Node *nex,*ch[26];
    bool b;
    int num;
    Node():nex(NULL),b(false),num(0){
        for(int i=0;i<26;i++)
            ch[i]=NULL;
    }
}*root;
struct Aho_Corasick_Automaton{
    inline void Insert(char *c){
        int len=strlen(c+1);
        Node *x=root;
        for(int i=1;i<=len;i++){
            int k=c[i]-'a';
            if(x->ch[k]==NULL) x->ch[k]=new Node;
            x=x->ch[k];
        }
        x->num++;
    }
    inline void GetFail(){
        queue<Node*>q;
        Node *x=root;
        for(int i=0;i<26;i++){
            if(x->ch[i]!=NULL) q.push(x->ch[i]),x->ch[i]->nex=x;
            else x->ch[i]=x;
        }
        while(!q.empty()){
            x=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(x->ch[i]!=NULL) q.push(x->ch[i]),x->ch[i]->nex=x->nex->ch[i];
                else x->ch[i]=x->nex->ch[i];
            }
            Node *tmp=x;
            tmp=tmp->nex;
            while(tmp!=root && !tmp->num) tmp=tmp->nex;
            x->nex=tmp;
        }
        return;
    }
    inline int Match(char *c){
        int len=strlen(c+1);
        int ans=0;
        Node *x=root;
        for(int i=1;i<=len;i++){
            int k=c[i]-'a';
            x=x->ch[k];
            Node *tmp=x;
            while(tmp!=root && !tmp->b){
                ans+=tmp->num,tmp->b=true;
                tmp=tmp->nex;
            }
        }
        return ans;
    }
}AC;
int main(){
    T=read();
    while(T--){
        root=new Node;
        n=read();
        for(int i=1;i<=n;i++){
            scanf("%s",c+1);
            AC.Insert(c);
        }
        AC.GetFail();
        scanf("%s",c+1);
        printf("%d\n",AC.Match(c));
    }
return 0;
}
0
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

AC自动机的简单Java实现

AC自动机主要实现多模式字符匹配的快速查找,相关知识点为: 1.trie树 2.KMP算法 代码有相关注释,如下: import java.util.ArrayList; import jav...
  • sqh201030412
  • sqh201030412
  • 2017-01-05 11:15
  • 1481

Trie、KMP、AC自动机小结

最近做了不字符串的题,做下小结吧~          首先是Trie(也叫前缀树),Trie的结构并不难理解,Trie是个树形结构,它的每条边对应一个字符,每个节点对应一个字符串的前缀(根节点对应空串...
  • qian99
  • qian99
  • 2014-02-05 21:58
  • 1399

NYOJ 1085 数单词 (AC自动机模板题)

数单词 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 为了能够顺利通过英语四六级考试,现在大家每天早上都会早起读英语。 LYH本来以为自己在6月份的考试中可以...
  • LYHVOYAGE
  • LYHVOYAGE
  • 2014-09-29 08:20
  • 1516

Duan2baka的各种LCA模板!

LCA,即最近公共祖先,是在有根树中两个点最近的公共祖先,在树上问题中非常有用QAQ常用LCA求法:一、树链剖分LCA树链剖分LCA,顾名思义,就是用树链剖分求LCA,两个节点从各自的重链往上跳,跳到...
  • WADuan2
  • WADuan2
  • 2017-10-17 22:02
  • 223

数据结构--AC自动机--模板2

病毒侵袭持续中 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Su...
  • u012845138
  • u012845138
  • 2014-03-17 20:41
  • 511

AC自动机模板

  • 2015-12-08 01:01
  • 1KB
  • 下载

洛谷 P3796 【模板】AC自动机(加强版)

题面传送门 题解 随便统计一下每个单词出现的次数 详见代码 #include #include #include #include #include using namespace std...
  • qq_35878547
  • qq_35878547
  • 3天前 07:28
  • 18

hdu 3065 病毒侵袭持续中 ac自动机模板题

窝今天果断翻了SB,main函数中忘记写ac.bfs()这句话了,然后各种单步调试感觉怎么这个fail数组那么奇怪呢...很无语...后来不小心发现了果断AC,基本和上一道题类似,不过就是第几个字符串...
  • azx736420641
  • azx736420641
  • 2015-09-03 13:11
  • 184

AC自动机模板(【CJOJ1435】)

题面Description对,这就是裸的AC自动机。 要求:在规定时间内统计出模版字符串在文本中出现的次数。Input第一行:模版字符串的个数N。 第2->N+1行:N个字符串。(每个模版字符串的...
  • qq_30974369
  • qq_30974369
  • 2017-07-06 16:49
  • 126

hdu 2896 病毒侵袭 ac自动机模板题

和上一道题不同的是这个题目的mark数组是标记一下到底是第几个串,因为匹配串中不同模式串个数不大于3,不过有可能相同串个数很多- -虽然我数组只开了10过了...还有就是字符的个数从26个飙升到127...
  • azx736420641
  • azx736420641
  • 2015-09-02 17:53
  • 145