Computer Virus on Planet Pandora
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 256000/128000 K (Java/Others)
Total Submission(s): 2847 Accepted Submission(s): 799
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.
3 2 AB DCB DACB 3 ABC CDE GHI ABCCDEFIHG 4 ABB ACDEE BBB FEEE A[2B]CD[4E]F
0 3 2HintIn 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自动机水题
/*************************************************************************
> File Name: hdu3695.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年02月04日 星期三 21时17分18秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int N = 5110000;
char str[1010];
char buf[N];
char input[N];
struct node
{
node *next[26]; //根据题目而定
node *fail;
int count;
node ()
{
fail = NULL;
for (int i = 0; i < 26; ++i)
{
next[i] = NULL;
}
count = 0;
}
};
node *qu[500010];
class AC_Automation
{
private:
node *root;
int head;
int tail;
public:
AC_Automation()
{
head = 0;
tail = 0;
root = new node();
}
void Build_Trie(char str[])
{
int len = strlen (str);
node *p = root;
for (int i = 0; i < len; ++i)
{
int ind = str[i] - 'A';
if (p -> next[ind] == NULL)
{
p -> next[ind] = new node();
}
p = p -> next[ind];
}
++p -> count;
}
void Build_AC ()
{
root -> fail = NULL;
qu[tail++] = root;
while (head < tail)
{
node *now = qu[head++];
node *p = NULL;
for (int i = 0; i < 26; ++i)
{
if (now -> next[i] != NULL)
{
if (now == root)
{
now -> next[i] -> fail = root;
}
else
{
p = now -> fail;
while (p != NULL)
{
if (p -> next[i] != NULL)
{
now -> next[i] -> fail = p -> next[i];
break;
}
else
{
p = p -> fail;
}
}
}
if (p == NULL)
{
now -> next[i] -> fail = root;
}
qu[tail++] = now -> next[i];
}
}
}
}
int Match (char buf[])
{
int ans = 0;
int len = strlen (buf);
node *p = root;
for (int i = 0; i < len; ++i)
{
int ind = buf[i] - 'A';
while (p -> next[ind] == NULL && p != root)
{
p = p -> fail;
}
p = p -> next[ind];
if (p == NULL)
{
p = root;
}
node *tmp = p;
while (tmp != root && tmp -> count != -1)
{
ans += tmp -> count;
tmp -> count = -1;
tmp = tmp -> fail;
}
}
return ans;
}
void dfs (node *p)
{
for (int i = 0; i < 26; ++i)
{
if (p -> next[i] != NULL)
{
dfs (p -> next[i]);
}
}
delete p;
}
~AC_Automation()
{
dfs (root);
}
};
int main ()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
AC_Automation AC;
for (int i = 1; i <= n; ++i)
{
scanf("%s", str);
AC.Build_Trie (str);
}
scanf("%s", input);
int len = strlen (input);
int cnt = 0;
for (int i = 0; i < len; ++i)
{
if (input[i] >= 'A' && input[i] <= 'Z')
{
buf[cnt++] = input[i];
}
else if (input[i] == '[')
{
int x = 0;
++i;
while (input[i] >= '0' && input[i] <= '9' && i < len)
{
x = x * 10 + input[i++] - '0';
}
for (int j = 0; j < x; ++j)
{
buf[cnt++] = input[i];
}
++i;
}
else if (input[i] == ']')
{
continue;
}
}
buf[cnt] = '\0';
AC.Build_AC();
int ans = AC.Match(buf);
for (int i = 0;i < cnt / 2; ++i)
{
swap (buf[i], buf[cnt - i - 1]);
}
ans += AC.Match(buf);
printf("%d\n", ans);
}
return 0;
}