ZOJ Problem Set - 3440
A virus is a sequence of letters that can be matched in the virus database.
Nowadays, viruses become complex. They have varieties. Fortunately, the database has the ability to precisely describe all varieties of viruses.
The database describes viruses using text records. A text record has the form
This define identification_label as content. The identification_label consists of lower-case letters (at least one letter). The content has four forms:
The virus is defined with the identification "virus".
It is guaranteed no recursive records. An illegal example:
virus:=[b] b:=[a] a:=[b]
This is not legal, either:
This is legal:
parta:=a|b|c virus:=[parta][partb][partb] partb:=d|e[subparta]h subparta:=fg|g
Input has at most 10 test cases, separated by one blank line.
Each case begins with an integer N, followed by N (1 ≤ N ≤ 12) lines of text records describing the virus. Then an integer M, followed by M (1 ≤ M ≤ 30) lines. Each line has one virus sample, which is a sequence of lower-case letters, may contain virus and is to be detected.
Each identification_label has 32 letters at most. Each content has 128 characters at most. Each virus sample has 2048 characters at most.
In one case, content of records are mostly just simple letters or [identification_label] (1st or 3rd form). Test cases are somehow simple enough to prevent you from Time Limit Exceed. Take it easy.
For each virus sample, if the virus can be detected, output
Output one blank line AFTER each test case.
4 parta:=a|b|c virus:=[parta][partb][partb] partb:=d|e[subparta]h subparta:=fg|g 2 abcdefghijklm nopqrstuvwxyz
Author: WU, Jun
Contest: Let's Celebrate the 100th Contest on ZOJ!