首页 > 代码库 > hdu 3695:Computer Virus on Planet Pandora(AC自动机,入门题)

hdu 3695:Computer Virus on Planet Pandora(AC自动机,入门题)

Computer Virus on Planet Pandora

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 256000/128000 K (Java/Others)
Total Submission(s): 2578    Accepted Submission(s): 713


Problem Description
    Aliens on planet Pandora also write computer programs like us. Their programs only consist of capital letters (‘A’ to ‘Z’) which they learned from the Earth. On 
planet Pandora, hackers make computer virus, so they also have anti-virus software. Of course they learned virus scanning algorithm from the Earth. Every virus has a pattern string which consists of only capital letters. If a virus’s pattern string is a substring of a program, or the pattern string is a substring of the reverse of that program, they can say the program is infected by that virus. Give you a program and a list of virus pattern strings, please write a program to figure out how many viruses the program is infected by.
 

 

Input
There are multiple test cases. The first line in the input is an integer T ( T<= 10) indicating the number of test cases.

For each test case:

The first line is a integer n( 0 < n <= 250) indicating the number of virus pattern strings.

Then n lines follows, each represents a virus pattern string. Every pattern string stands for a virus. It’s guaranteed that those n pattern strings are all different so there
are n different viruses. The length of pattern string is no more than 1,000 and a pattern string at least consists of one letter.

The last line of a test case is the program. The program may be described in a compressed format. A compressed program consists of capital letters and 
“compressors”. A “compressor” is in the following format:

[qx]

q is a number( 0 < q <= 5,000,000)and x is a capital letter. It means q consecutive letter xs in the original uncompressed program. For example, [6K] means 
‘KKKKKK’ in the original program. So, if a compressed program is like:

AB[2D]E[7K]G

It actually is ABDDEKKKKKKKG after decompressed to original format.

The length of the program is at least 1 and at most 5,100,000, no matter in the compressed format or after it is decompressed to original format.
 

 

Output
For each test case, print an integer K in a line meaning that the program is infected by K viruses.
 

 

Sample Input
3
2
AB
DCB
DACB
3
ABC
CDE
GHI
ABCCDEFIHG
4
ABB
ACDEE
BBB
FEEE
A[2B]CD[4E]F
 

 

Sample Output
0
3
2
Hint
In the second case in the sample input, the reverse of the program is ‘GHIFEDCCBA’, and ‘GHI’ is a substring of the reverse, so the program is infected by virus ‘GHI’.
 

 

Source
2010 Asia Fuzhou Regional Contest
 

 

Recommend
chenyongfu   |   We have carefully selected several similar problems for you:  3699 3692 3691 3698 3697 
 
  AC自动机,入门题
  在hdu上过了,但是poj没过。hdu要求2000MS,poj竟然要求1000MS,太禽兽了 = =。
  另外附上一张ac自动机,trie树,trie图,后缀树,后缀树组等之间关系的图示:
  代码参考于:HDU 3695 / POJ 3987 Computer Virus on Planet Pandora(AC自动机)(2010 Asia Fuzhou Regional Contest)
  题意
  给你T组测试数据,每组测试数据有n个模式串,后面跟着一个母串,你需要输出母串包含模式串的个数。
  母串有的需要展开。
  思路
  根据输入的模式串构造trie图(反转串也算),然后根据trie图进行匹配,用isv[]记录匹配到的模式串,最后统计一共匹配到多少模式串。
  注意
  如果母串包含一个模式串的反转也算。
  代码
  1 #include <iostream>  2 #include <string.h>  3 #include <stdio.h>  4 #include <queue>  5 #include <algorithm>  6 using namespace std;  7   8 #define MAXN 260  9 #define MAXS 5100010 10  11  12 char ss[MAXS],s[MAXS];    //母串和翻译后的母串 13  14 struct Node{ 15     Node* next[26]; 16     Node* fail;    //失败指针 17     bool isv;    //当前这个串走过了没有 18     int id;        //这个串的编号 19  20     Node() 21     { 22         memset(next,NULL,sizeof(next)); 23         fail = NULL; 24         isv = false; 25         id = 0; 26     } 27  28     ~Node()    //析构函数 29     { 30         int i; 31         for(i=0;i<26;i++) 32             if(next[i]) 33                 delete(next[i]); 34     } 35 }; 36  37 void Insert(Node* p,char t[],int id)    //将t插入到Trie树中 38 { 39     int i; 40     for(i=0;t[i];i++){ 41         int tt = t[i] - A; 42         if(!p->next[tt]) 43             p->next[tt] = new Node; 44         p = p->next[tt]; 45     } 46     p->id = id; 47 } 48  49 void setFail(Node* root)    //构建失败指针 50 { 51     queue <Node*> q; 52     Node* cur; 53     cur = root; 54     q.push(cur); 55     while(!q.empty()){ 56         cur = q.front(); 57         q.pop(); 58         int i; 59         for(i=0;i<26;i++){ 60             if(!cur->next[i])    //当前方向的节点是空节点 61                 continue; 62             if(cur==root)    //当前节点是root,他的下一个节点的fail指针全部指向root 63                 cur->next[i]->fail = root; 64             Node* t = cur->fail; 65             while(t!=NULL && !t->next[i])    //找到下一个节点存在或者t走到了根节点的fail指针处NULL 66                 t = t->fail; 67             if(t) 68                 cur->next[i]->fail = t->next[i]; 69             else  70                 cur->next[i]->fail = root; 71  72             q.push(cur->next[i]); 73         } 74     } 75     root->fail = root; 76 } 77  78 bool isv[MAXN]; 79 void Index(Node* root,char s[])    //母串利用ac自动机进行匹配,将匹配成功的模式串编号标记到isv中 80 { 81     int i; 82     Node* p = root; 83     for(i=0;s[i];i++){ 84         int t = s[i]-A; 85         while(p!=root && !p->next[t])    //找到根节点或者找到对应节点 86             p = p->fail; 87         if(p->next[t]) 88             p = p->next[t]; 89         Node* q = p; 90         //每走过一个点就把这个点对应的所有失败节点走一遍,标记已经走过 91         while(q!=root && !q->isv){ 92             q->isv = true; 93             if(q->id>0) 94                 isv[q->id] = true; 95             q = q->fail; 96         } 97     } 98 } 99 100 void Trans(char ss[],char s[])    //将ss展开翻译成s101 {102     int i;103     int j=0,num=0;104     for(i=0;ss[i];i++){105         if(  (a<=ss[i] && ss[i]<=z)    106           || (A<=ss[i] && ss[i]<=Z))    //如果是字母107           s[j++] = ss[i];108         else if( 0<=ss[i] && ss[i]<=9)    //如果是数字,计数109             num = num*10 + int(ss[i]-0);110         else if( ss[i]==] )    //如果是‘]‘,将‘]‘前的字符复制num-1遍111             while(--num)112                 s[j++] = ss[i-1];113     }114     s[j] = \0;115 }116 117 int getAns(int n)    //利用isv获得最终结果118 {119     int i,sum=0;120     for(i=1;i<=n;i++)121         sum += isv[i];122     return sum;123 }124 125 int main()126 {127     int T,n,i;128     scanf("%d",&T);129     while(T--){130         Node* root = new Node;131         scanf("%d",&n);132         //输入n个模式串133         for(i=1;i<=n;i++){134             char t[1010];135             scanf("%s",t);136             Insert(root,t,i);137             reverse(t,t + strlen(t));    //翻转138             Insert(root,t,i);139         }140         //构建失败指针141         setFail(root);142         //输入母串143         scanf("%s",ss);144         Trans(ss,s);    //展开145         //匹配,获得结果146         memset(isv,0,sizeof(isv));147         Index(root,s);    //用ac自动机开始匹配母串148         printf("%d\n",getAns(n));    //根据匹配数据获得结果149         delete root;150     }151     return 0;152 }

 

Freecode : www.cnblogs.com/yym2013