HDU 2896 病毒侵袭（AC自动机）-白红宇

HDU 2896 病毒侵袭（AC自动机）

阅读量：4072 次

发布时间：2019-05-25

本文共 3076 字，大约阅读时间需要 10 分钟。

链接：

题目：

Problem Description

当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~

但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。

万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~

Input

第一行，一个整数N（1<=N<=500），表示病毒特征码的个数。

接下来N行，每行表示一个病毒特征码，特征码字符串长度在20—200之间。

每个病毒都有一个编号，依此为1—N。

不同编号的病毒特征码不会相同。

在这之后一行，有一个整数M（1<=M<=1000），表示网站数。

接下来M行，每行表示一个网站源码，源码字符串长度在7000—10000之间。

每个网站都有一个编号，依此为1—M。

以上字符串中字符都是ASCII码可见字符（不包括回车）。

Output

依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。

web 网站编号: 病毒编号病毒编号 …

冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。

最后一行输出统计信息，如下格式

total: 带病毒网站数

冒号后有一个空格。

Sample Input

3aaabbbccc2aaabbbcccbbaacc

Sample Output

web 1: 1 2 3total: 1

分析与总结：

AC自动机的模板题，这题需要注意的是字符范围是“可见字符”， ASCII码范围是33~126。因为这个原因RE了很多次。

另外，我的代码竟然很神奇地跑到了rank1

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int MAX_NODE = 1000005;const int SIGMA_SIZE = 126-32;char str[10005];bool  hash[600];struct node{    node* fail;    node* next[SIGMA_SIZE];    int id;    int count;    void init(){        id=0; count=0;        memset(next, 0, sizeof(next));    }};class AC_Automation{public:    void init();    void insert(char* str, int id);    void getFail();    bool find(char* str);private:    node* new_node();    node Heap[MAX_NODE];    node* root;    int size;};node* AC_Automation::new_node(){    Heap[size].init();    return &Heap[size++];}void AC_Automation::init(){    size=0;     root = new_node();}void AC_Automation::insert(char* str,int id){    node* p=root;    for( ; *str; ++str){        int ch=*str-33;        if(p->next[ch] == NULL)            p->next[ch] = new_node();        p = p->next[ch];    }    p->id=id;     ++p->count;}void AC_Automation::getFail(){    queue
       
         Q;    Q.push(root);    while(!Q.empty()){        node* tmp=Q.front(); Q.pop();        for(int i=0; i
        
         next[i]; if(now != NULL){ Q.push(now); if(tmp==root) now->fail=root; else{ node* p=tmp->fail; while(p != NULL){ if(p->next[i] != NULL){ now->fail = p->next[i]; break; } p = p->fail; } if(p==NULL) now->fail=root; } } else{ if(tmp==root) now=root; else now=tmp->fail->next[i]; } } }}bool AC_Automation::find(char* str){ node* p=root; bool ok=false; memset(hash, 0, sizeof(hash)); for( ; *str; ++str){ int ch=*str-33; p = p->next[ch]; if(p==NULL) p=root; node* tmp=p; while(tmp!=root && tmp->count){ if(tmp->count){ ok=true; hash[tmp->id] = true; } tmp = tmp->fail; } } return ok;}AC_Automation ac;int main(){ int n,m; char code[205]; scanf("%d%*c",&n); ac.init(); for(int i=1; i<=n; ++i){ gets(code); ac.insert(code,i); } ac.getFail(); scanf("%d%*c",&m); int cnt=0; for(int i=1; i<=m; ++i){ gets(str); if(ac.find(str)){ ++cnt; printf("web %d:", i); for(int j=1; j<=n; ++j)if(hash[j]){ printf(" %d",j); } puts(""); } } printf("total: %d\n",cnt); return 0;}

—— 生命的意义，在于赋予它意义士。

原创 ， By D_Double (转载请标明)

你可能感兴趣的文章

mmo游戏开发应在profile下运行，才能保证正式运行不卡