1609 - AntiVirus
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 401
Solved: 104
- Description
- Rocket323 is an engineer(码畜) in an anti-virus software company. One day, he discovered some signatures of a new virus. He wants to know whether his computer is infected with that virus or not?
In this problem, a computer program is a string consists of lowercase English letters. The signature of the new virus is also a string consist of lowercase English letters. The program is infected with the virus if the program consists of at least one signature.
Rocket323 is very curious, so you have to tell him how many signatures appeared in the program.
Because the program is too long, it’s given to you in a compressed format.
- Input
- There are multiple test cases. The first line consists of only a integer T (T <= 30) indicating the number of test cases.
For each test case:
The first line contains an integer N (0 < N <= 2000) indicating the number of signatures.
Then n lines follows, each represents a signature of the new virus. It’s guaranteed that the signatures only consist of lowercase English letters and each signature is not empty. The length of each signature is no more than 150 and these N strings are all different.
The last line of each test case is the computer program.
The program will be described in a compressed format. A compressed string consists of lowercase English letters and “compressors”. A “compressor” is in the following format:
[qx]
q is a number(0 < q <= 10^9) and x is a lowercase English letter. It means q consecutive letter x(s) in the original uncompressed string. For example, [6k] means “kkkkkk” (without the quotes) in the original string. So, if a compressed string is like:
ab[2d]e[7k]g
It actually is “abddekkkkkkkg”(without the quotes) after decompressed to original format.
The length of the compressed program is at least 1 and at most 10^6.
The length of the decompressed program is at most 5 * 10^14.
Note that the signature will never be given in the compressed format!
- Output
- For each test case:
Print string “Yes”(without the quotes) if the program is infected with the virus, otherwise print “No”(without the quotes), then print the number of signature appeared in the program separated by a space.
Sorry for the trouble caused.
- sample input
-
4 2 ab dcb dacb 3 a ab abc dabc 2 a ab [5a]b[4a]b 3 ab cd ef abcdef
- sample output
-
No 0 Yes 3 Yes 2 Yes 3
- hint
- source
- The 7th(2012) ACM Programming Contest of HUST Problem Setter: Yang Xiao