Computer Virus on Planet Pandora
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 256000/128000 K (Java/Others)
Total Submission(s): 2879 Accepted Submission(s): 808
Problem 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.
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.
波比源码 » HDU 3695 Computer Virus on Planet Pandora (AC自动机)
Great post thank you. Hello Administ . Onwin , Onwin Giriş , Onwin Güncel Giriş , Tiklayin. Onwin