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
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.
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.
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’.
AC自动机，入门题
题意
思路
注意
代码
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std; #define MAXN 260
#define MAXS 5100010 char ss[MAXS],s[MAXS]; //母串和翻译后的母串 struct Node{
Node* next[];
Node* fail; //失败指针
bool isv; //当前这个串走过了没有
int id; //这个串的编号 Node()
{
memset(next,NULL,sizeof(next));
fail = NULL;
isv = false;
id = ;
} ~Node() //析构函数
{
int i;
for(i=;i<;i++)
if(next[i])
delete(next[i]);
}
}; void Insert(Node* p,char t[],int id) //将t插入到Trie树中
{
int i;
for(i=;t[i];i++){
int tt = t[i] - 'A';
if(!p->next[tt])
p->next[tt] = new Node;
p = p->next[tt];
}
p->id = id;
} void setFail(Node* root) //构建失败指针
{
queue <Node*> q;
Node* cur;
cur = root;
q.push(cur);
while(!q.empty()){
cur = q.front();
q.pop();
int i;
for(i=;i<;i++){
if(!cur->next[i]) //当前方向的节点是空节点
continue;
if(cur==root) //当前节点是root，他的下一个节点的fail指针全部指向root
cur->next[i]->fail = root;
Node* t = cur->fail;
while(t!=NULL && !t->next[i]) //找到下一个节点存在或者t走到了根节点的fail指针处NULL
t = t->fail;
if(t)
cur->next[i]->fail = t->next[i];
else
cur->next[i]->fail = root; q.push(cur->next[i]);
}
}
root->fail = root;
} bool isv[MAXN];
void Index(Node* root,char s[]) //母串利用ac自动机进行匹配，将匹配成功的模式串编号标记到isv中
{
int i;
Node* p = root;
for(i=;s[i];i++){
int t = s[i]-'A';
while(p!=root && !p->next[t]) //找到根节点或者找到对应节点
p = p->fail;
if(p->next[t])
p = p->next[t];
Node* q = p;
//每走过一个点就把这个点对应的所有失败节点走一遍，标记已经走过
while(q!=root && !q->isv){
q->isv = true;
if(q->id>)
isv[q->id] = true;
q = q->fail;
}
}
} void Trans(char ss[],char s[]) //将ss展开翻译成s
{
int i;
int j=,num=;
for(i=;ss[i];i++){
if( ('a'<=ss[i] && ss[i]<='z')
|| ('A'<=ss[i] && ss[i]<='Z')) //如果是字母
s[j++] = ss[i];
else if( ''<=ss[i] && ss[i]<='') //如果是数字，计数
num = num* + int(ss[i]-'');
else if( ss[i]==']' ) //如果是']'，将']'前的字符复制num-1遍
while(--num)
s[j++] = ss[i-];
}
s[j] = '\0';
} int getAns(int n) //利用isv获得最终结果
{
int i,sum=;
for(i=;i<=n;i++)
sum += isv[i];
return sum;
} int main()
{
int T,n,i;
scanf("%d",&T);
while(T--){
Node* root = new Node;
scanf("%d",&n);
//输入n个模式串
for(i=;i<=n;i++){
char t[];
scanf("%s",t);
Insert(root,t,i);
reverse(t,t + strlen(t)); //翻转
Insert(root,t,i);
}
//构建失败指针
setFail(root);
//输入母串
scanf("%s",ss);
Trans(ss,s); //展开
//匹配，获得结果
memset(isv,,sizeof(isv));
Index(root,s); //用ac自动机开始匹配母串
printf("%d\n",getAns(n)); //根据匹配数据获得结果
delete root;
}
return ;
}
Freecode : www.cnblogs.com/yym2013