5103 - Computer Virus on Planet Pandora Description
Asia - Fuzhou - 2010/2011 |
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.
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 < n250) 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 < q5, 000, 000) and x is a capital letter. It means q consecutive letter x's 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.
For each test case, print an integer K in a line meaning that the program is infected by K viruses.
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'.
3
2
AB
DCB
DACB
3
ABC
CDE
GHI
ABCCDEFIHG
4
ABB
ACDEE
BBB
FEEE
A[2B]CD[4E]F
0
3
2
Fuzhou 2010-2011
AC 自動機。。。
1 #include <iostream>
2 #include <cstdio>
3
4 using namespace std;
5
6 const int ACTC = 26;
7 const int ACTM = 200000;
8 const int ACQL = ACTM;
9
10 struct AC
11 {
12 int count;
13 AC *fail;
14 AC *ch[ ACTC ];
15 };
16
17 AC *que[ ACQL ];
18
19 AC* ac_new( bool init = false ) {
20 int i;
21 AC *p;
22 static AC memAC[ ACTM ];
23 static int tot = 0;
24 if ( init ) {
25 tot = 0;
26 return 0;
27 }
28 p = memAC + tot++;
29 p->count = 0;
30 p->fail = 0;
31 for ( i = 0; i < ACTC; ++i )
32 p->ch[ i ] = 0;
33 return p;
34 }
35
36 int ac_add( AC* &root, const char *first, const char *last ) {
37 AC ** p = &root;
38 for ( ; ; ) {
39 if ( *p == 0 ) *p = ac_new();
40 if ( first == last ) return ++( (*p)->count );
41 p = &( (*p)->ch[ *first++ ] );
42 }
43 }
44
45 void ac_build( AC *root ) {
46 // root != 0
47 int qh = 0, qt = 1, i;
48 AC *pf, *pc, *pt;
49 root->fail = 0;
50 que[ 0 ] = root;
51 while ( qh != qt ) {
52 pf = que[ qh ];
53 qh = ( qh + 1 ) % ACQL;
54 for ( i = 0; i < ACTC; ++i ) {
55 if ( pc = pf->ch[ i ] ) {
56 for ( pt = pf->fail; pt && ( pt->ch[ i ] == 0 ); pt = pt->fail )
57 ;
58 pc->fail = pt ? pt->ch[ i ] : root;
59 que[ qt ] = pc;
60 qt = ( qt + 1 ) % ACQL;
61 }
62 }
63 }
64 }
65
66 int ac_query( AC *root, const char *first, const char *last ) {
67 // root != 0
68 int ans = 0;
69 AC *p = root, *q;
70 while ( first != last ) {
71 while ( p && ( p->ch[ *first ] == 0 ) ) {
72 p = p->fail;
73 }
74 if ( p ) {
75 q = p = p->ch[ *first++ ];
76 while ( q && ( q->count != -1 ) ) {
77 ans += q->count;
78 q->count = -1;
79 q = q->fail;
80 }
81 }
82 else {
83 p = root;
84 ++first;
85 }
86 }
87 return ans;
88 }
89
90 char txt[ 5100009 ], pat[ 1009 ];
91 AC *root;
92
93 void expand( char *out ) {
94 char ch;
95 char *q = out;
96 ch = getchar();
97 while ( (ch!='\n') && (ch!=EOF) ) {
98 if ( ('A'<=(ch)) && ((ch)<='Z') ) {
99 *q++ = ch;
100 }
101 else {
102 ch = getchar();
103 int num = 0;
104 while ( ('0'<=(ch)) && ((ch)<='9') ) {
105 num = num * 10 + ( ch - '0' );
106 ch = getchar();
107 }
108 while ( num-- > 0 ) {
109 *q++ = ch;
110 }
111 ch = getchar();
112 }
113 ch = getchar();
114 }
115 *q = 0;
116 }
117
118 int main() {
119 int td, n, ans;
120 char *pc, *ph, *pt;
121 scanf( "%d", &td );
122 while ( td-- ) {
123 scanf( "%d%*c", &n );
124 ac_new( true );
125 root = 0;
126 while ( n-- ) {
127 gets( pat );
128 for ( pc = pat; *pc; ++pc )
129 *pc -= 'A';
130 ac_add( root, pat, pc );
131 }
132 ac_build( root );
133 expand( txt );
134 for ( pc = txt; *pc; ++pc )
135 *pc -= 'A';
136 ans = ac_query( root, txt, pc );
137 ph = txt;
138 pt = pc - 1;
139 while ( ph < pt ) {
140 char tmp = *ph;
141 *ph = *pt;
142 *pt = tmp;
143 ++ph;
144 --pt;
145 }
146 ans += ac_query( root, txt, pc );
147 printf( "%d\n", ans );
148 }
149 return 0;
150 }
151