coreBugZJ

此 blog 已弃。

Computer Virus on Planet Pandora Description, ACM/ICPC 2010/2011 亚洲,福州区域赛 F, UVA 5103

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.

 

Input 

There are multiple test cases. The first line in the input is an integer T (T$ \le$10) indicating the number of test cases.

For each test case:

The first line is a integer n (0 < n$ \le$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$ \le$5, 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.

 

Output 

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'.

 

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

 


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 ( *== 0 ) *= 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 *= 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 *= 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         *= 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 


posted on 2011-03-25 19:27 coreBugZJ 阅读(1894) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理