Time Limit:2000MS Memory Limit:128000KB 64bit IO Format:%I64d & %I64u
System Crawler (2014-11-05)
Description
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
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
Sample Input
2
AB
DCB
DACB
3
ABC
CDE
GHI
ABCCDEFIHG
4
ABB
ACDEE
BBB
FEEE
A[2B]CD[4E]F
Sample Output
3
2
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std; struct Trie
{
int next[500010][26],fail[500010],end[500010];
int root,L;
int newnode()
{
for(int i = 0;i < 26;i++)
next[L][i] = -1;
end[L++] = 0;
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = 0;i < len;i++)
{
if(next[now][buf[i]-'A'] == -1)
next[now][buf[i]-'A'] = newnode();
now = next[now][buf[i]-'A'];
}
end[now]++;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = 0;i < 26;i++)
if(next[root][i] == -1)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while( !Q.empty() )
{
int now = Q.front();
Q.pop();
for(int i = 0;i < 26;i++)
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int query(char buf[])
{
int len = strlen(buf);
int now = root;
int res = 0;
for(int i = 0;i < len;i++)
{
now = next[now][buf[i]-'A'];
int temp = now;
while( temp != root )
{
res += end[temp];
end[temp] = 0;
temp = fail[temp];
}
}
return res;
}
void debug()
{
for(int i = 0;i < L;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = 0;j < 26;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
}
};
char buf[5100010];
char buf2[5100010];
Trie ac;
void rever(char * arr,int len){
len--;
for(int i=0;i<=len/2;i++)swap(arr[i],arr[len-i]);
}
void read(int ind,int & ans,int & gap){
ans=0;gap=0;
for(int i=ind;buf[i]<='9'&&buf[i]>='0';i++){
gap++;
ans*=10;
ans+=buf[i]-'0';
}
}
int main()
{
int T;
int n;
scanf("%d",&T);
while( T-- )
{
scanf("%d",&n);
ac.init();
for(int i = 0;i < n;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%s",buf);
int i=0,j=0;
for(i=0,j=0;buf[i];){
if(buf[i]<='Z'&&buf[i]>='A')buf2[j++]=buf[i++];
else if(buf[i]=='['){
int len,gap;
read(i+1,len,gap);
i+=gap+1;
for(int k=0;k<min(len,1005);k++)buf2[j++]=buf[i];
i+=2;
}
}
buf2[j]=0;
int ans=ac.query(buf2);
rever(buf2,j);
ans+=ac.query(buf2);
printf("%d\n",ans);
}
return 0;
}